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. The problem of testing if a given graph is a PCG is not known to be NP-hard yet. To obtain a complete characterization of PCGs is a wide open problem in computational biology and graph theory. In the literature, most witness trees admitted by known PCGs are stars and caterpillars. In this paper, we give 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.