In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

area of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a -leaf power of a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

whose vertices are the leaves of and whose edges connect pairs of leaves whose

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...

in is at most . That is, is an

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definit ...

of the graph power , induced by the leaves of . For a graph constructed in this way, is called a -leaf root of . A graph is a leaf power if it is a -leaf power for some . These graphs have applications in

phylogeny A phylogenetic tree (also phylogeny or evolutionary tree Felsenstein J. (2004). ''Inferring Phylogenies'' Sinauer Associates: Sunderland, MA.) is a branching diagram or a tree showing the evolutionary relationships among various biological spe ...

, 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. 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 it is shown that

interval graph In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. ...

s 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 -leaf powers for bounded values of have bounded

clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum nu ...

, but this is not true of leaf powers with unbounded exponents.

Structure and recognition

A graph is a 3-leaf power if and only if it is a (bull, dart, gem)-free

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...

. Based on this characterization and similar ones, 3-leaf powers can be recognized in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

. Characterizations of 4-leaf powers are given by and , 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) and Ducoffe (2018), respectively. For the recognition problem of -leaf powers was unsolved for a long time, but showed that -leaf powers can be recognized in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

for any fixed . However, the high dependency on the parameter makes this algorithm unsuitable for practical use. Also, it has been proved that recognizing -leaf powers is

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...

when parameterized by and the degeneracy of the input graph.

Notes

References

*. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. {{refend Graph families Perfect graphs