×

Characterizing star-PCGs. (English) Zbl 1479.05340

Summary: 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}\le d_{\max}\) such that \(G\) has an edge between two vertices \(u,v\in 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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
05C12 Distance in graphs
05C22 Signed and weighted graphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Booth, S.; Lueker, S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci., 13, 335-379 (1976) · Zbl 0367.68034
[2] Brandstädt, A.: On leaf powers. Technical report, University of Rostock (2010) · Zbl 1225.05079
[3] Calamoneri, T.; Frascaria, D.; Sinaimeri, B., All graphs with at most seven vertices are pairwise compatibility graphs, Comput. J., 56, 7, 882-886 (2013)
[4] Calamoneri, T.; Frangioni, A.; Sinaimeri, B., Pairwise compatibility graphs of caterpillars, Comput. J., 57, 11, 1616-1623 (2014)
[5] Calamoneri, T.; Petreschi, R., On pairwise compatibility graphs having Dilworth number two, Theor. Comput. Sci., 524, 34-40 (2014) · Zbl 1283.05142
[6] Calamoneri, T.; Petreschi, R., On pairwise compatibility graphs having Dilworth number \(k\), Theor. Comput. Sci., 547, 82-89 (2014) · Zbl 1420.05046
[7] Calamoneri, T.; Petreschi, R.; Sinaimeri, B., On the pairwise compatibility property of some superclasses of threshold graphs, Discrete Math. Algorithms Appl., 5, 2, 360002 (2013) · Zbl 1271.05026
[8] Calamoneri, T.; Sinaimeri, B., Pairwise compatibility graphs: a survey, SIAM Rev., 58, 3, 445-460 (2016) · Zbl 1342.05058
[9] Chen, Z-Z; Jiang, T.; Lin, G., Computing phylogenetic roots with bounded degrees and errors, SIAM J. Comput., 32, 864-879 (2003) · Zbl 1053.68069
[10] Durocher, S.; Mondal, D.; Rahman, MdS, On graphs that are not PCGs, Theor. Comput. Sci., 571, 78-87 (2015) · Zbl 1306.05085
[11] Felsenstein, J., Cases in which parsimony or compatibility methods will be positively misleading, Syst. Zool., 27, 401-410 (1978)
[12] Hossain, MdI; Salma, SA; Rahman, MdS; Mondal, D., A necessary condition and a sufficient condition for pairwise compatibility graphs, J. Graph Algorithms Appl., 21, 3, 341-352 (2017) · Zbl 1358.05237
[13] Kearney, PE; Munro, JI; Phillips, D.; Benson, G.; Page, R., Efficient generation of uniform samples from phylogenetic trees, Algorithms in Bioinformatics, LNCS 2812, 177-189 (2003), Berlin: Springer, Berlin
[14] Lin, G.; Kearney, PE; Jiang, T.; Goos, G.; Hartmanis, J.; van Leeuwen, J.; Lee, DT; Teng, S-H, Phylogenetic k-root and Steiner k-root, Algorithms and Computation, LNCS 1969, 539-551 (2000), Berlin: Springer, Berlin · Zbl 1044.68704
[15] Mehnaz, S., Rahman, M.S.: Pairwise compatibility graphs revisited. In: Proceedings of the 2013 International Conference on Informatics, Electronics Vision (ICIEV), pp. 1-6 (2013)
[16] Nishimura, N.; Ragde, P.; Thilikos, DM, On graph powers for leaf-labeled trees, J. Algorithms, 42, 69-108 (2002) · Zbl 0990.68100
[17] Salma, SA; Rahman, MdS; Hossain, MdI, Triangle-free outerplanar 3-graphs are pairwise compatibility graphs, J. Graph Algorithms Appl., 17, 81-102 (2013) · Zbl 1260.05044
[18] Xiao, M.; Nagamochi, H., Some reduction operations to pairwise compatibility graphs, Inf. Process. Lett., 153 (2020) · Zbl 1481.05150
[19] Yanhaona, MN; Bayzid, MdS; Rahman, MdS, Discovering pairwise compatibility graphs, Discrete Math. Algorithm Appl., 2, 4, 607-624 (2010) · Zbl 1216.05138
[20] Yanhaona, MN; Hossain, KSMT; Rahman, MdS, Pairwise compatibility graphs, J. Appl. Math. Comput., 30, 479-503 (2009) · Zbl 1180.68204
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.