Pairwise compatibility graphs revisited
Shagufta Mehnaz, M. Sohel Rahman · 2013
A graph G = (V, E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dminand dmaxsuch that each leaf luof T corresponds to a vertex u ∈ V and there is an edge (u, v) ∈ E if and only if dmin≤ dT(lu, lv) ≤ dmaxwhere dT(lu, lv) is the sum of weights of the edges on the unique path from luto lvin T. In this note, firstly, we show a class of bipartite graphs not to be PCG, that is, it is not possible to draw a pairwise compatibility tree for these graphs. Further we construct a class of more general non-PCGs each member of which contains a bipartite graph belonging to the class of graphs mentioned above as a subgraph. Secondly, we show by computational means that all the bipartite graphs with at most eight vertices are PCGs. In particular all these graphs are PCGs of a particular structure of tree called centipede.