×

Exact-2-relation graphs. (English) Zbl 1447.05198

Summary: Pairwise compatibility graphs (PCGs) with non-negative integer edge weights recently have been used to describe rare evolutionary events and scenarios with horizontal gene transfer. Here we consider the case that vertices are separated by exactly two discrete events: Given a tree \(T\) with leaf set \(L\) and edge-weights \(\lambda : E ( T ) \to \mathbb{N}_0\), the non-negative integer pairwise compatibility graph \(\text{nniPCG} ( T , \lambda , 2 , 2 )\) has vertex set \(L\) and \(x y\) is an edge whenever the sum of the non-negative integer weights along the unique path from \(x\) to \(y\) in \(T\) equals 2. A graph \(G\) has a representation as \(\text{nniPCG} ( T , \lambda , 2 , 2 )\) if and only if its point-determining quotient \(G/\overset{\bullet}{\sim}\) is a block graph, where two vertices are in relation \(\overset{\bullet}{\sim}\) if they have the same neighborhood in \(G\). If \(G\) is of this type, a labeled tree \(( T , \lambda )\) explaining \(G\) can be constructed efficiently. In addition, we consider an oriented version of this class of graphs.

MSC:

05C90 Applications of graph theory
92D10 Genetics and epigenetics
05C20 Directed graphs (digraphs), tournaments
05C05 Trees
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahmed, S.; Rahman, M. S., Multi-interval pairwise compatibility graphs, (Gopal, T. V.; Jäger, G.; Steila, S., Theory and Applications of Models of Computation (14’Th TAMC 2017). Theory and Applications of Models of Computation (14’Th TAMC 2017), Lect. Notes Comp. Sci., vol. 10185 (2017), Springer: Springer Heidelberg), 71-84 · Zbl 1485.68170
[2] Baiocchi, P.; Calamoneri, T.; Monti, A.; Petreschi, R., Graphs that are not pairwise compatible: A new proof technique, (Iliopoulos, C.; Leong, H. W.; Sung, W.-K., Combinatorial Algorithms, 29th IWOCA. Combinatorial Algorithms, 29th IWOCA, Lecture Notes Comp. Sci., vol. 10979 (2018), Springer: Springer Berlin, Heidelberg), 39-51 · Zbl 1511.05197
[3] Baiocchi, P.; Calamoneri, T.; Monti, A.; Petreschi, R., Some classes of graphs that are not PCGs, Theoret. Comput. Sci., 791, 62-75 (2019) · Zbl 1433.05307
[4] Bandelt, H.-J.; Mulder, H. M., Distance-hereditary graphs, J. Combin. Theory Ser. B, 41, 182-208 (1986) · Zbl 0605.05024
[5] Brandstädt, A.; Hundt, C., Ptolemaic graphs and interval graphs are leaf powers, (Laber, E. S.; Bornstein, C. F.; Nogueira, L. T.; L., F., LATIN 2008. LATIN 2008, Lect. Notes Comp. Sci., vol. 4957 (2008), Springer: Springer Berlin), 479-491 · Zbl 1136.68450
[6] Brandstädt, A.; Lea, V. B.; Rautenbach, D., Exact leaf powers, Theoret. Comput. Sci., 411, 2968-2977 (2010) · Zbl 1193.05141
[7] Bull, J. J.; Pease, C. M., Combinatorics and variety of mating-type systems, Evolution, 43, 667-671 (1989)
[8] Buneman, P., The recovery of trees from measures of dissimilarity, (Hodson, F. R.; Kendall, D. G.; Tautu, P., Mathematics in the Archaeological and Historical Sciences (1971), Edinburgh University Press: Edinburgh University Press Edinburgh), 387-395
[9] Burzyn, P.; Bonomo, F.; Durán, G., NP-completeness results for edge modification problems, Discrete Appl. Math., 154, 1824-1844 (2006) · Zbl 1110.68094
[10] Calamoneri, T.; Frangioni, A.; Sinaimeri, B., Pairwise compatibility graphs of Caterpillars, Comput. J., 57, 1616-1623 (2014)
[11] Calamoneri, T.; Montefusco, E.; Petreschi, R.; Sinaimeria, B., Exploring pairwise compatibility graphs, Theoret. Comput. Sci., 468, 23-36 (2013) · Zbl 1258.05104
[12] Calamoneri, T.; Sinaimeri, B., Pairwise compatibility graphs: A survey, SIAM Rev., 58, 445-460 (2016) · Zbl 1342.05058
[13] Chaudhuri, K.; Chen, K.; Mihaescu, R.; Rao, S., On the tandem duplication-random loss model of genome rearrangement, (Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithm (SODA ’06) (2006), Soc. Industrial Appl. Math.: Soc. Industrial Appl. Math. Philadelphia), 564-570 · Zbl 1192.92017
[14] Crespelle, C.; Paul, C., Fully dynamic recognition algorithm and certificate for directed cographs, Discrete Appl. Math., 154, 1722-1741 (2006) · Zbl 1110.68096
[15] Dress, A. W.M.; Huber, K. T.; Koolen, J.; Moulton, V.; Spillner, A., Basic Phylogenetic Combinatorics (2012), Cambridge University Press: Cambridge University Press Cambridge UK · Zbl 1298.92008
[16] Geiß, M.; Anders, J.; Stadler, P. F.; Wieseke, N.; Hellmuth, M., Reconstructing gene trees from fitch’s xenology relation, J. Math. Biol., 77, 1459-1491 (2017) · Zbl 1396.05025
[17] Gessel, I.; Li, J., Enumeration of point-determining graphs, J. Combin. Theory Ser. A, 118, 591-612 (2011) · Zbl 1238.05136
[18] Hammack, R.; Imrich, W.; Klavžar, S., Handbook of product graphs (2011), CRC Press: CRC Press Boca Raton · Zbl 1283.05001
[19] Harary, F., A characterization of block-graphs, Canadian Math. Bull., 6, 1-6 (1963) · Zbl 0112.25002
[20] Hellmuth, M.; Hernandez-Rosales, M.; Huber, K. T.; Moulton, V.; Stadler, P. F.; Wieseke, N., Orthology relations, symbolic ultrametrics, and cographs, J. Math. Biol., 66, 399-420 (2013) · Zbl 1408.05038
[21] Hellmuth, M.; Hernandez-Rosales, M.; Long, Y.; Stadler, P. F., Inferring phylogenetic trees from the knowledge of rare evolutionary events, J. Math. Biol., 76, 1623-1653 (2017) · Zbl 1386.05186
[22] Hellmuth, M.; Long, Y.; Geiß, M.; Stadler, P. F., A short note on undirected fitch graphs, Art Discrete Appl. Math. (ADAM), 1 (2018), P1.08 · Zbl 1421.05076
[23] Hossain, M. I.; Salma, S. A.; Rahman, M. S.; Mondal, D., A necessary condition and a sufficient condition for pairwise compatibility graphs, J. Graph. Algorithms Appl., 21, 341-352 (2017) · Zbl 1358.05237
[24] Imrich, W., Factoring cardinal product graphs in polynomial time, Discrete Math., 192, 119-144 (1998) · Zbl 0955.68089
[25] Kearney, P. E.; Munro, J. I.; Phillips, D., Efficient generation of uniform samples from phylogenetic trees, (Algorithms in Bioinformatics (WABI 2003 Budapest). Algorithms in Bioinformatics (WABI 2003 Budapest), Lect. Notes Comp. Sci., vol. 2812 (2003), Springer: Springer Berlin), 177-189
[26] Kilibarda, G., Enumeration of unlabelled mating graphs, Graphs Combin., 23, 183-199 (2007) · Zbl 1116.05038
[27] Luo, H.; Arndt, W.; Zhang, Y.; Shi, G.; Alekseyev, M. A.; Tang, J.; Hughes, A. L.; Friedman, R., Phylogenetic analysis of genome rearrangements among five mammalian orders, Mol. Phylogenet. Evol., 65, 871-882 (2012)
[28] McKenzie, R., Cardinal multiplication of structures with a reflexive relation, Fund. Math., 70, 59-101 (1971) · Zbl 0228.08002
[29] Nishimura, N.; Ragde, P.; Thilikos, D. M., On graph powers for leaf-labeled trees, J. Algorithms, 42, 69-108 (2002) · Zbl 0990.68100
[30] Rokas, A.; Holland, P., Rare genomic changes as a tool for phylogenetics, Trends Ecol. Evol., 15, 454-459 (2000)
[31] Salma, S. A.; Rahman, M. S.; Hossain, M. I., Triangle-free outerplanar 3-graphs are pairwise compatibility graphs, J. Graph. Algorithms Appl., 17, 81-102 (2013) · Zbl 1260.05044
[32] Semple, C.; Steel, M., Phylogenetics (2003), Oxford University Press: Oxford University Press Oxford UK · Zbl 1043.92026
[33] Shamir, R.; Sharan, R.; Thur, D., Cluster graph modification problems, Discrete Appl. Math., 144, 173-182 (2004) · Zbl 1068.68107
[34] Simões-Pereira, J. M.S., A note on the tree realizability of a distance matrix, J. Combin. Theory, 6, 303-310 (1969) · Zbl 0177.26903
[35] Sritharan, R., Graph modification problem for some classes of graphs, J. Discrete Algorithms, 38-41, 32-37 (2016) · Zbl 1355.68107
[36] Sumner, D. P., Point determination in graphs, Discrete Math., 5, 179-187 (1973) · Zbl 0265.05124
[37] Tarver, J. E.; Sperling, E. A.; Nailor, A.; Heimberg, A. M.; Robinson, J. M.; King, B. L.; Pisani, D.; Donoghue, P. C.J.; Peterson, K. J., Mirnas: Small genes with big potential in metazoan phylogenetics, Mol. Biol. Evol., 30, 2369-2382 (2013)
[38] (Waegele, J.; Bartholomaeus, T. W., Deep Metazoan Phylogeny: The Backbone of the Tree of Life—New Insights from Analyses of Molecules, Morphology, and Theory of Data Analysis (2014), De Gruyter)
[39] Yanhaona, M. N.; Hossain, K. S.M. T.; Rahman, M. S., 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.