DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
Abstract
Let T be an edge weighted tree, let dT(u, v) be the sum of the weights of the edges on the path from u to v in T, and let dmin and dmax be two non-negative real numbers such that dmin ≤ dmax. Then a pairwise compatibility graph of T for dmin and dmax is a graph G = (V, E), where each vertex u' ∈ V corresponds to a leaf u of T and there is an edge (u', v') ∈ E if and only if dmin ≤ dT(u, v) ≤ dmax. A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two non-negative real numbers dmin and dmax such that G is a pairwise compatibility graph of T for dmin and dmax. Kearney et al. conjectured that every graph is a PCG [3]. In this paper, we refute the conjecture by showing that not all graphs are PCGs. Moreover, we recognize several classes of graphs as pairwise compatibility graphs. We identify two restricted classes of bipartite graphs as PCG. We also show that the well known tree power graphs and some of their extensions are PCGs.
References
-
T. H. Cormen , Introduction to Algorithms ( MIT Press , Cambridge , 2001 ) . Google Scholar -
N. C. Jones and P. A. Pevzner , An Introduction to Bioinformatics Algorithms ( MIT Press , Cambridge , 2004 ) . Google Scholar P. Kearney , J. I. Munro and D. Phillips , Efficient generation of uniform samples from phylogenetic trees, Proc. of WABI 20032812,LNBI (Springer, 2003) pp. 177–189. Google Scholar-
A. M. Lesk , Introduction to Bioinformatics ( Oxford University Press , Great Clarendon Street, Oxford , 2002 ) . Google Scholar G. H. Lin , P. E. Kearney and T. Jiang , Phylogenetic k-root and Steiner k-root, Proc. of International Conference on Algorithms and Computation (ISAAC 2000)1969,LNCS (Springer, 2000) pp. 539–551. Google Scholar- D. Phillips, Uniform sampling from phylogenetic trees, Master's thesis, University of Waterloo, August (2002) . Google Scholar
- J. Global Optim. 4, 301 (1994), DOI: 10.1007/BF01098364. Crossref, Google Scholar
M. N. Yanhaona , M. S. Bayzid and M. S. Rahman , Discovering Pairwise compatibility graphs, Proc. 16th International Computing and Combinatorics Conference (COCOON 2010)6196,Lecture Notes in Computer Science (2010) pp. 399–408. Google Scholar- J. Appl. Math. Comput. 30, 479 (2009), DOI: 10.1007/s12190-008-0204-7. Crossref, Google Scholar
