Some Reduction Operations to Pairwise Compatibility Graphs
share
A graph G=(V,E) with a vertex set V and an edge set E is called a pairwise compatibility graph (PCG, for short) if there are a tree T whose leaf set is V, a non-negative edge weight w in T, and two non-negative reals d_≤ d_ such that G has an edge uv∈ E if and only if the distance between u and v in the weighted tree (T,w) is in the interval [d_, d_]. PCG is a new graph class motivated from bioinformatics. In this paper, we give some necessary and sufficient conditions for PCG based on cut-vertices and twins, which provide reductions among PCGs. Our results imply that complete k-partite graph, cactus, and some other graph classes are subsets of PCG.
READ FULL TEXT