In the mathematical area of graph theory, a k-leaf power of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves whose distance in is at most . That is, is an induced subgraph of the graph power , induced by the leaves of . For a graph constructed in this way, is called a k-leaf root of .
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. 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 and such graphs are a proper subclass of strongly chordal graphs.
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.
Structure and recognition
|Unsolved problem in computer science:|
Is there a polynomial time algorithm for recognizing leaf powers or -leaf powers for ?(more unsolved problems in computer science)
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.
- Nishimura, Ragde & Thilikos (2002).
- Dahlhaus & Duchet (1987); Lubiw (1987); Raychaudhuri (1992).
- Brandstädt et al. (2010); Hayward, Kearney & Malton (2002).
- Broin & Lowe (1986); Bibelnieks & Dearing (1993).
- Brandstädt & Hundt (2008); Gurski & Wanke (2009).
- Dom et al. (2006); Rautenbach (2006)
- Brandstädt & Le (2006).
- 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, MR 2472761.
- Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Rooted directed path graphs are leaf powers", Discrete Mathematics, 310: 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: 133–138, 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: 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, 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, MR 2499471.
- Hayward, R.B.; Kearney, P.E.; Malton, A. (2002), "NeST graphs", Discrete Applied Mathematics, 121: 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, doi:10.1006/jagm.2001.1195.
- Rautenbach, D. (2006), "Some remarks about leaf roots", Discrete Mathematics, 306: 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.