Abstract
Let T be an edge weighted tree, let d T (u,v) be the sum of the weights of the edges on the path from u to v in T, and let d min and d max be two non-negative real numbers such that d min ≤ d max . Then a pairwise compatibility graph of T for d min and d max 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 d min ≤ d T (u, v) ≤ d max . A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two non-negative real numbers d min and d max such that G is a pairwise compatibility graph of T for d min and d max . 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. We also show that the well known tree power graphs and some of their extensions are PCGs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, Cambridge (2001)
Jones, N.C., Pevzner, P.A.: An Introduction to Bioinformatics Algorithms. The MIT Press, Cambridge (2004)
Kearney, P., Munro, I., Phillips, D.: Efficient Generation of Uniform Samples from Phylogenetic Trees. In: Benson, G., Page, R.D.M. (eds.) WABI 2003. LNCS (LNBI), vol. 2812, pp. 177–189. Springer, Heidelberg (2003)
Lesk, A.M.: Introduction to Bioinformatics. Oxford University Press, Oxford (2002)
Lin, G.H., Jiang, T., Kearney, P.E.: Phylogenetic k-root and steiner k-root. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol. 1969, pp. 539–551. Springer, Heidelberg (2000)
Phillips, D.: Uniform Sampling From Phylogenetics Trees. Master’s thesis, University of Waterloo (August 2002)
Yanhaona, M.N., Hossain, K.S.M.T., Rahman, M.S.: Pairwise compatibility graphs. Journal of Applied Mathematics and Computing 30, 479–503 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yanhaona, M.N., Bayzid, M.S., Rahman, M.S. (2010). Discovering Pairwise Compatibility Graphs. In: Thai, M.T., Sahni, S. (eds) Computing and Combinatorics. COCOON 2010. Lecture Notes in Computer Science, vol 6196. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14031-0_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-14031-0_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14030-3
Online ISBN: 978-3-642-14031-0
eBook Packages: Computer ScienceComputer Science (R0)