Leaf power

In the mathematical area of graph theory, a tree T is a k-leaf root of a graph G = (V,E) if V is contained in the set of leaves of T and for vertices x,y in V, xy is an edge in E if and only if their distance in T is at most k. Then G is called a k-leaf power.

A graph is a leaf power if it is a k-leaf power for some k.^[1] This is an important class of graphs based on phylogeny.

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]

It is easy to see that a graph is a 2-leaf power if and only if it is the disjoint union of cliques (i.e., a P₃-free graph).

A graph is a 3-leaf power if and only if it is a (bull,dart,gem)-free chordal graph.^[5]

Based on this characterization and similar ones, 3-leaf powers can be recognized in linear time.^[6]

Characterizations of 4-leaf powers are given in ^[7] which also enable linear time recognition.

For k > 5 the recognition problem of k-leaf powers is open, and likewise it is an open problem whether leaf powers can be recognized in polynomial time.

In^[8] it is shown that interval graphs and the larger class of rooted directed path graphs are leaf powers.

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 (2006)
5. Dom et al. (2006),Rautenbach (2006)
6. Brandstädt & Le (2006)
7. Rautenbach (2006),Brandstädt, Le & Sritharan (2008)
8. Brandstädt et al. (2010)

References

• Bibelnieks, E.; Dearing, P.M. (2006), "Neighborhood subtree tolerance graphs", Discrete Applied Mathematics 98: 133–138.
• Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Rooted directed path graphs are leaf powers", Discrete Mathematics 310: 897–910.
• Brandstädt, Andreas; Le, Van Bang (2006), "Structure and linear time recognition of 3-leaf powers", Information Processing Letters 98: 133–138.
• Brandstädt, Andreas; Le, Van Bang; Sritharan, R. (2008), "Structure and linear time recognition of 4-leaf powers", ACM Transactions on Algorithms 5: Article 11.
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Broin, M.W.; Lowe, T.J. (1986), "Neighborhood subtree tolerance graphs", SIAM J. Algebraic and Discrete Meth. 7: 348–357.
• 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: 363–381.
• Farber, M. (1983), "Characterizations of strongly chordal graphs", Discrete Mathematics 43 (2–3): 173–189, doi:10.1016/0012-365X(83)90154-1.
• Hayward, R.B.; Kearney, P.E.; Malton, A. (2002), "NeST graphs", Discrete Applied Mathematics 121: 139–153.
• 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.
• Rautenbach, D. (2006), "Some remarks about leaf roots", Discrete Mathematics 306: 1456–1461.
• Raychaudhuri, A. (1992), "On powers of strongly chordal graphs and circular arc graphs", Ars Combinatoria 34: 147–160.