Leaf power
In the mathematical area of graph theory, a k-leaf power of a tree T is a graph G whose vertices are the leaves of T and whose edges connect pairs of leaves whose distance in T is at most k. That is, G is an induced subgraph of the graph power [math]\displaystyle{ T^k }[/math], induced by the leaves of T. For a graph G constructed in this way, T is called a k-leaf root of G.
A graph is a leaf power if it is a k-leaf power for some 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 Hundt) 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
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), 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 k ≥ 7 the recognition problem of k-leaf powers was unsolved for a long time, but (Lafond 2021) showed that k-leaf powers can be recognized in polynomial time for any fixed k. However, the high dependency on the parameter k makes this algorithm unsuitable for practical use.
Also, it has been proved that recognizing k-leaf powers is fixed-parameter tractable when parameterized by k and the degeneracy of the input graph.[10]
Notes
- ↑ Nishimura, Ragde & Thilikos (2002).
- ↑ (Dahlhaus Duchet); (Lubiw 1987); (Raychaudhuri 1992).
- ↑ (Brandstädt Hundt); (Hayward Kearney).
- ↑ (Broin Lowe); (Bibelnieks Dearing).
- ↑ (Brandstädt Hundt); (Gurski Wanke).
- ↑ (Dom Guo); (Rautenbach 2006)
- ↑ Brandstädt & Le (2006).
- ↑ Ko, Ming-Tat; Chang, Maw-Shang (2007-06-21). "The 3-Steiner Root Problem" (in en). Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science. 4769. Springer, Berlin, Heidelberg. pp. 109–120. doi:10.1007/978-3-540-74839-7_11. ISBN 9783540748380.
- ↑ Ducoffe, Guillaume (2018-10-04). "Polynomial-time Recognition of 4-Steiner Powers". arXiv:1810.02304 [cs.CC].
- ↑ Eppstein, David; Havvaei, Elham (2020-08-01). "Parameterized Leaf Power Recognition via Embedding into Graph Products" (in en). Algorithmica 82 (8): 2337–2359. doi:10.1007/s00453-020-00720-8. ISSN 1432-0541. https://doi.org/10.1007/s00453-020-00720-8.
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.
- "Rooted directed path graphs are leaf powers", Discrete Mathematics 310 (4): 897–910, 2010, doi:10.1016/j.disc.2009.10.006.
- "Structure and linear time recognition of 3-leaf powers", Information Processing Letters 98 (4): 133–138, 2006, doi:10.1016/j.ipl.2006.01.004.
- "Structure and linear time recognition of 4-leaf powers", ACM Transactions on Algorithms 5: 1–22, 2008, doi:10.1145/1435375.1435386.
- 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, https://archive.org/details/graphclassessurv0000bran.
- 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. (2006), "Error compensation in leaf root problems", Algorithmica 44 (4): 363–381, doi:10.1007/s00453-005-1180-z.
- 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.
- 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.
- Lafond, Manuel (2021), "Recognizing k-leaf powers in polynomial time, for constant k", Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA): 1384–1410.
- "Doubly lexical orderings of matrices", SIAM Journal on Computing 16 (5): 854–879, 1987, 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, 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, https://drops.dagstuhl.de/opus/volltexte/2019/10217/.
 |  |
