Jump to content

Leaf power

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by OAbot (talk | contribs) at 01:22, 16 April 2020 (Open access bot: doi added to citation with #oabot.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

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 .

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

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 -leaf powers for ?

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 k ≥ 7 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.

Notes

  1. ^ a b 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. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. pp. 109–120. doi:10.1007/978-3-540-74839-7_11. ISBN 9783540748380. {{cite book}}: |journal= ignored (help)
  9. ^ Ducoffe, Guillaume (2018-10-04). "Polynomial-time Recognition of 4-Steiner Powers". arXiv:1810.02304 [cs.CC].

References