leaf power

Since powers of strongly chordal graphs are strongly chordal and trees are strongly chordal, it follows that leaf powers are strongly chordal graphs.{{harvtxt|Dahlhaus|Duchet|1987}}; {{harvtxt|Lubiw|1987}}; {{harvtxt|Raychaudhuri|1992}}.

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{{harvtxt|Brandstädt|Hundt|Mancini|Wagner|2010}}; {{harvtxt|Hayward|Kearney|Malton|2002}}. and such graphs are a proper subclass of strongly chordal graphs.{{harvtxt|Broin|Lowe|1986}}; {{harvtxt|Bibelnieks|Dearing|1993}}.

In {{harvtxt|Brandstädt|Hundt|Mancini|Wagner|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 {{mvar|k}}-leaf powers for bounded values of {{mvar|k}} have bounded clique-width, but this is not true of leaf powers with unbounded exponents.{{harvtxt|Brandstädt|Hundt|2008}}; {{harvtxt|Gurski|Wanke|2009}}.

A graph is a 3-leaf power if and only if it is a (bull, dart, gem)-free chordal graph.{{harvtxt|Dom|Guo|Hüffner|Niedermeier|2006}}; {{harvtxt|Rautenbach|2006}}

Based on this characterization and similar ones, 3-leaf powers can be recognized in linear time.{{sfnp|Brandstädt|Le|2006}}

Characterizations of 4-leaf powers are given by {{harvtxt|Rautenbach|2006}} and {{harvtxt|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){{Cite book|last1=Ko|first1=Ming-Tat|last2=Chang|first2=Maw-Shang|title=Graph-Theoretic Concepts in Computer Science |chapter=The 3-Steiner Root Problem |date=2007-06-21|series=Lecture Notes in Computer Science|volume=4769 |language=en|publisher=Springer, Berlin, Heidelberg|pages=109–120|doi=10.1007/978-3-540-74839-7_11|isbn=9783540748380}} and Ducoffe (2018),{{cite arXiv|last=Ducoffe|first=Guillaume|date=2018-10-04|title=Polynomial-time Recognition of 4-Steiner Powers|eprint=1810.02304|class=cs.CC}} respectively.

For {{math|k ≥ 7}} the recognition problem of {{mvar|k}}-leaf powers was unsolved for a long time, but {{harvtxt|Lafond|2021}} showed that {{mvar|k}}-leaf powers can be recognized in polynomial time for any fixed {{mvar|k}}. However, the high dependency on the parameter {{mvar|k}} makes this algorithm unsuitable for practical use.

Also, it has been proved that recognizing {{mvar|k}}-leaf powers is fixed-parameter tractable when parameterized by {{mvar|k}} and the degeneracy of the input graph.{{Cite journal|last1=Eppstein|first1=David|last2=Havvaei|first2=Elham|date=2020-08-01|title=Parameterized Leaf Power Recognition via Embedding into Graph Products|url=https://doi.org/10.1007/s00453-020-00720-8|journal=Algorithmica|language=en|volume=82|issue=8|pages=2337–2359|doi=10.1007/s00453-020-00720-8|s2cid=218988055|issn=1432-0541|arxiv=1810.02452}}

{{reflist|30em}}

{{refbegin|30em}}

• {{citation

| last1 = Bibelnieks | first1 = E.

| last2 = Dearing | first2 = P.M.

| title = Neighborhood subtree tolerance graphs

| journal = Discrete Applied Mathematics

| volume = 43

| pages = 13–26

| year = 1993

| doi = 10.1016/0166-218X(93)90165-K

| doi-access =

}}.

• {{citation

| last1 = Brandstädt | first1 = Andreas

| last2 = Hundt | first2 = Christian

| contribution = Ptolemaic graphs and interval graphs are leaf powers

| doi = 10.1007/978-3-540-78773-0_42

| mr = 2472761

| pages = 479–491

| publisher = Springer, Berlin

| series = Lecture Notes in Comput. Sci.

| title = LATIN 2008: Theoretical informatics

| volume = 4957

| year = 2008| isbn = 978-3-540-78772-3

}}.

• {{citation

| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt

| last2 = Hundt | first2 = Christian

| last3 = Mancini | first3 = Federico

| last4 = Wagner | first4 = Peter

| title = Rooted directed path graphs are leaf powers

|journal = Discrete Mathematics

| volume = 310

| issue = 4 | pages = 897–910

| year = 2010 | doi=10.1016/j.disc.2009.10.006

| doi-access = free}}.

• {{citation

| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt

| last2 = Le | first2 = Van Bang

| title = Structure and linear time recognition of 3-leaf powers

| journal = Information Processing Letters

| volume = 98

| issue = 4 | pages = 133–138

| year = 2006

| doi=10.1016/j.ipl.2006.01.004

| citeseerx = 10.1.1.144.3486 }}.

• {{citation

| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt

| last2 = Le | first2 = Van Bang

| last3 = Sritharan | first3 = R.

| title = Structure and linear time recognition of 4-leaf powers

| journal = ACM Transactions on Algorithms

| volume = 5

| pages = 1–22

| year = 2008

| doi = 10.1145/1435375.1435386 | s2cid = 6114466 }}.

• {{citation

| last1 = Brandstädt

| first1 = Andreas

| author1-link = Andreas Brandstädt

| last2 = Le

| first2 = Van Bang

| last3 = Spinrad

| first3 = Jeremy

| title = Graph Classes: A Survey

| publisher = SIAM Monographs on Discrete Mathematics and Applications

| year = 1999

| isbn = 978-0-89871-432-6

| url-access = registration

| url = https://archive.org/details/graphclassessurv0000bran

}}.

• {{citation

| last1 = Broin | first1 = M.W.

| last2 = Lowe | first2 = T.J.

| title = Neighborhood subtree tolerance graphs

| journal = SIAM J. Algebr. Discrete Methods

| volume = 7

| pages = 348–357

| year = 1986

| doi = 10.1137/0607039

}}.

• {{citation

| last1 = Dahlhaus | first1 = E.

| last2 = Duchet | first2 = P.

| journal = Ars Combinatoria

| pages = 23–30

| title = On strongly chordal graphs

| volume = 24 B

| year = 1987}}.

• {{citation

| last1 = Dahlhaus | first1 = E.

| last2 = Manuel | first2 = P. D.

| last3 = Miller | first3 = M.

| doi = 10.1016/S0012-365X(97)00268-9

| issue = 1–3

| journal = Discrete Mathematics

| pages = 269–271

| title = A characterization of strongly chordal graphs

| volume = 187

| year = 1998| doi-access =

}}.

• {{citation

| last1 = Dom | first1 = M.

| last2 = Guo | first2 = J.

| last3 = Hüffner | first3 = F.

| last4 = Niedermeier | first4 = R. | author4-link=Rolf Niedermeier

| journal = Algorithmica

| pages = 363–381

| title = Error compensation in leaf root problems

| volume = 44

| issue = 4

| year = 2006 | doi=10.1007/s00453-005-1180-z| citeseerx = 10.1.1.218.490

| s2cid = 75279

}}.

• {{citation

| last = Farber | first = M.

| doi = 10.1016/0012-365X(83)90154-1

| issue = 2–3

| journal = Discrete Mathematics

| pages = 173–189

| title = Characterizations of strongly chordal graphs

| volume = 43

| year = 1983| doi-access =

}}.

• {{citation

| last1 = Gurski | first1 = Frank

| last2 = Wanke | first2 = Egon

| doi = 10.1016/j.dam.2008.08.031

| issue = 4

| journal = Discrete Applied Mathematics

| mr = 2499471

| pages = 583–595

| title = The NLC-width and clique-width for powers of graphs of bounded tree-width

| volume = 157

| year = 2009| doi-access = free

}}.

• {{citation

| last1 = Hayward | first1 = R.B.

| last2 = Kearney | first2 = P.E.

| last3 = Malton | first3 = A.

| journal = Discrete Applied Mathematics

| pages = 139–153

| title = NeST graphs

| volume = 121

| year = 2002 | issue = 1–3

| doi=10.1016/s0166-218x(01)00207-4| doi-access = free

}}.

• {{citation

| last = Lafond | first = Manuel

| arxiv=2110.15421

| journal = Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

| pages = 1384–1410

| title = Recognizing k-leaf powers in polynomial time, for constant k

| year = 2021

}}.

• {{citation

| last = Lubiw | first = A. | author-link = Anna Lubiw

| doi = 10.1137/0216057

| issue = 5

| journal = SIAM Journal on Computing

| pages = 854–879

| title = Doubly lexical orderings of matrices

| volume = 16

| year = 1987}}.

• {{citation

| last = McKee | first = T. A.

| doi = 10.1016/S0012-365X(99)00107-7

| issue = 1–3

| journal = Discrete Mathematics

| pages = 245–247

| title = A new characterization of strongly chordal graphs

| volume = 205

| year = 1999| doi-access = free

}}.

• {{citation

| last1 = Nishimura | first1 = N.

| last2 = Ragde | first2 = P.

| last3 = Thilikos | first3 = D.M.

| journal = Journal of Algorithms

| pages = 69–108

| title = On graph powers for leaf-labeled trees

| volume = 42

| year = 2002 | doi=10.1006/jagm.2001.1195| citeseerx = 10.1.1.43.1127

}}.

• {{citation

| last = Rautenbach | first = D.

| year = 2006

|journal = Discrete Mathematics

| pages = 1456–1461

| title = Some remarks about leaf roots

| volume = 306

| issue = 13

| doi=10.1016/j.disc.2006.03.030| doi-access =

}}.

• {{citation

| last = Raychaudhuri | first = A.

| year = 1992

| journal = Ars Combinatoria

| pages = 147–160

| title = On powers of strongly chordal graphs and circular arc graphs

| volume = 34}}.

• {{citation

| last1 = Eppstein | first1 = D.

| last2 = Havvaei | first2 = H.

| year = 2020

| journal = Algorithmica

| pages = 2337–2359

| title = Parameterized Leaf Power Recognition via Embedding into Graph Products

| volume = 82

| issue = 8

| doi=10.1007/s00453-020-00720-8

| s2cid = 218988055

| url = https://drops.dagstuhl.de/opus/volltexte/2019/10217/

| arxiv = 1810.02452

}}.

{{refend}}

Category:Graph families

Category:Perfect graphs