Journal Version
T. Calamoneri, B. Sinaimeri
Abstract
A graph G=(V,E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers m and M such that each leaf u of T is a node of V and there is an edge (u,v) in E if and only if m <= dT (u, v) <= M where dT (u, v) is the sum of weights of the edges on the unique path from u to v in T. In this paper, we survey the state of the art concerning this class of graphs and some of its subclasses.
PDF Files