Leaf power

In the mathematical area of graph theory, a k-leaf power of a tree ${\displaystyle T}$ is a graph ${\displaystyle G}$ whose vertices are the leaves of ${\displaystyle T}$ and whose edges connect pairs of leaves whose distance in ${\displaystyle T}$ is at most ${\displaystyle k}$. That is, ${\displaystyle G}$ is an induced subgraph of the graph power ${\displaystyle T^{k}}$, induced by the leaves of ${\displaystyle T}$. For a graph ${\displaystyle G}$ constructed in this way, ${\displaystyle T}$ is called a k-leaf root of ${\displaystyle G}$.

A tree (top) and its corresponding 3-leaf power (bottom)

A graph is a leaf power if it is a ${\displaystyle k}$-leaf power for some ${\displaystyle k}$.[1] These graphs have applications in phylogeny, the problem of reconstructing evolutionary trees.

Related classes of graphs

Since powers of strongly chordal graphs are strongly chordal and trees are strongly chordal, it follows that leaf powers are strongly chordal graphs.[2] Actually, leaf powers form a proper subclass of strongly chordal graphs; a graph is a leaf power if and only if it is a fixed tolerance NeST graph[3] and such graphs are a proper subclass of strongly chordal graphs.[4]

In Brandstädt et al. (2010) it is shown that interval graphs and the larger class of rooted directed path graphs are leaf powers. The indifference graphs are exactly the leaf powers whose underlying trees are caterpillar trees.

The k-leaf powers for bounded values of k have bounded clique-width, but this is not true of leaf powers with unbounded exponents.[5]

Structure and recognition

Unsolved problem in computer science: Is there a polynomial-time algorithm for recognizing leaf powers or ${\displaystyle k}$-leaf powers for ${\displaystyle k\geq 7}$? (more unsolved problems in computer science)

A graph is a 2-leaf power if and only if it is the disjoint union of cliques (i.e., a cluster graph).[1]

A graph is a 3-leaf power if and only if it is a (bull, dart, gem)-free chordal graph.[6] Based on this characterization and similar ones, 3-leaf powers can be recognized in linear time.[7]

Characterizations of 4-leaf powers are given by Rautenbach (2006) and Brandstädt, Le & Sritharan (2008), which also enable linear time recognition. Recognition of the 5-leaf and 6-leaf power graphs are also solved in linear time by Chang and Ko (2007)[8] and Ducoffe (2018),[9] respectively.

For ${\displaystyle k}$ ≥ 7 the recognition problem of ${\displaystyle k}$-leaf powers is open, and likewise, it is an open problem whether leaf powers can be recognized in polynomial time. However, it has been proved that recognizing ${\displaystyle k}$-leaf powers is fixed-parameter tractable when parameterized by ${\displaystyle k}$ and the degeneracy of the input graph.[10]

Notes

1. Nishimura, Ragde & Thilikos (2002).
2. Dahlhaus & Duchet (1987); Lubiw (1987); Raychaudhuri (1992).
3. Brandstädt et al. (2010); Hayward, Kearney & Malton (2002).
4. Broin & Lowe (1986); Bibelnieks & Dearing (1993).
5. Brandstädt & Hundt (2008); Gurski & Wanke (2009).
6. Dom et al. (2006); Rautenbach (2006)
7. Brandstädt & Le (2006).
8. Ko, Ming-Tat; Chang, Maw-Shang (2007-06-21). The 3-Steiner Root Problem. Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. pp. 109–120. doi:10.1007/978-3-540-74839-7_11. ISBN 9783540748380.
9. Ducoffe, Guillaume (2018-10-04). "Polynomial-time Recognition of 4-Steiner Powers". arXiv:1810.02304 [cs.CC].
10. Eppstein, David; Havvaei, Elham (2020-08-01). "Parameterized Leaf Power Recognition via Embedding into Graph Products". Algorithmica. 82 (8): 2337–2359. doi:10.1007/s00453-020-00720-8. ISSN 1432-0541. S2CID 218988055.

References

• Bibelnieks, E.; Dearing, P.M. (1993), "Neighborhood subtree tolerance graphs", Discrete Applied Mathematics, 43: 13–26, doi:10.1016/0166-218X(93)90165-K.
• Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemaic graphs and interval graphs are leaf powers", LATIN 2008: Theoretical informatics, Lecture Notes in Comput. Sci., 4957, Springer, Berlin, pp. 479–491, doi:10.1007/978-3-540-78773-0_42, ISBN 978-3-540-78772-3, MR 2472761.
• Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Rooted directed path graphs are leaf powers", Discrete Mathematics, 310 (4): 897–910, doi:10.1016/j.disc.2009.10.006.
• Brandstädt, Andreas; Le, Van Bang (2006), "Structure and linear time recognition of 3-leaf powers", Information Processing Letters, 98 (4): 133–138, CiteSeerX 10.1.1.144.3486, doi:10.1016/j.ipl.2006.01.004.
• Brandstädt, Andreas; Le, Van Bang; Sritharan, R. (2008), "Structure and linear time recognition of 4-leaf powers", ACM Transactions on Algorithms, 5: 1–22, doi:10.1145/1435375.1435386, S2CID 6114466.
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6.
• Broin, M.W.; Lowe, T.J. (1986), "Neighborhood subtree tolerance graphs", SIAM J. Algebr. Discrete Methods, 7: 348–357, doi:10.1137/0607039.
• Dahlhaus, E.; Duchet, P. (1987), "On strongly chordal graphs", Ars Combinatoria, 24 B: 23–30.
• Dahlhaus, E.; Manuel, P. D.; Miller, M. (1998), "A characterization of strongly chordal graphs", Discrete Mathematics, 187 (1–3): 269–271, doi:10.1016/S0012-365X(97)00268-9.
• Dom, M.; Guo, J.; Hüffner, F.; Niedermeier, R. (2006), "Error compensation in leaf root problems", Algorithmica, 44 (4): 363–381, CiteSeerX 10.1.1.218.490, doi:10.1007/s00453-005-1180-z, S2CID 75279.
• Farber, M. (1983), "Characterizations of strongly chordal graphs", Discrete Mathematics, 43 (2–3): 173–189, doi:10.1016/0012-365X(83)90154-1.
• Gurski, Frank; Wanke, Egon (2009), "The NLC-width and clique-width for powers of graphs of bounded tree-width", Discrete Applied Mathematics, 157 (4): 583–595, doi:10.1016/j.dam.2008.08.031, MR 2499471.
• Hayward, R.B.; Kearney, P.E.; Malton, A. (2002), "NeST graphs", Discrete Applied Mathematics, 121 (1–3): 139–153, doi:10.1016/s0166-218x(01)00207-4.
• Lubiw, A. (1987), "Doubly lexical orderings of matrices", SIAM Journal on Computing, 16 (5): 854–879, doi:10.1137/0216057.
• McKee, T. A. (1999), "A new characterization of strongly chordal graphs", Discrete Mathematics, 205 (1–3): 245–247, doi:10.1016/S0012-365X(99)00107-7.
• Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms, 42: 69–108, CiteSeerX 10.1.1.43.1127, doi:10.1006/jagm.2001.1195.
• Rautenbach, D. (2006), "Some remarks about leaf roots", Discrete Mathematics, 306 (13): 1456–1461, doi:10.1016/j.disc.2006.03.030.
• Raychaudhuri, A. (1992), "On powers of strongly chordal graphs and circular arc graphs", Ars Combinatoria, 34: 147–160.
• Eppstein, D.; Havvaei, H. (2020), "Parameterized Leaf Power Recognition via Embedding into Graph Products", Algorithmica, 82 (8): 2337–2359, doi:10.1007/s00453-020-00720-8, S2CID 218988055.