Characterizing Star-PCGs

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T, w, d min, d max) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d min = d max such that G has an edge between two vertices u, v. V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [d min, d max]. The tree T is also called a witness tree of the PCG G. How to recognize PCGs is a wide-open problem in the literature. This paper gives a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.