Rooted directed path graphs are leaf powers
Leaf powers are a graph class which has been introduced to model the problem of reconstructing phylogenetic trees. A graph \(G=(V,E)\) is called \(k\)-leaf power if it admits a \(k\)-leaf root, i.e., a tree \(T\) with leaves \(V\) such that \(uv\) is an edge in \(G\) if and only if the distance between \(u\) and \(v\) in \(T\) is at most \(k\). Moroever, a graph is simply called leaf power if it is a \(k\)-leaf power for some natural number \(k\). This paper characterizes leaf powers in terms of their relation to several other known graph classes. It also addresses the problem of deciding whether a given graph is a \(k\)-leaf power. The authors show that the class of leaf powers coincides with fixed tolerance NeST graphs, a well-known graph class with absolutely different motivations. After this, they provide the largest currently known proper subclass of leaf powers, i.e., the class of rooted directed path graphs. Subsequently, they study the leaf rank problem, the algorithmic challenge of determining the minimum \(k\) for which a given graph is a \(k\)-leaf power. Firstly, they give a lower bound on the leaf rank of a graph in terms of the complexity of its separators. Secondly, they use this measure to show that the leaf rank is unbounded on both the class of ptolemaic and the class of unit interval graphs. Finally, they provide efficient algorithms to compute \(2|V|\)-leaf roots for given ptolemaic or (unit) interval graphs \(G = (V,E)\).
- A Characterization of Comparability Graphs and of Interval Graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- A characterization of ptolemaic graphs
- A Class of Balanced Matrices Arising from Location Problems
- A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
- Characterizations of strongly chordal graphs
- Coloring powers of graphs of bounded clique-width.
- Consecutive retrieval property -- revisited
- Distance-hereditary graphs
- Error compensation in leaf power problems
- Graph Classes: A Survey
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 3839362 (Why is no real title available?)
- Neighborhood subtree tolerance graphs
- NeST graphs
- On graph powers for leaf-labeled trees
- On k- Versus (k + 1)-Leaf Powers
- On the clique-width of some perfect graph classes
- Ptolemaic Graphs and Interval Graphs Are Leaf Powers
- Simplicial Powers of Graphs
- Some remarks about leaf roots
- Strictly chordal graphs are leaf powers
- Structure and linear time recognition of 3-leaf powers
- The 3-Steiner Root Problem
- The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
- Topics in Intersection Graph Theory
- Tree spanners on chordal graphs: complexity and algorithms
- The complete inclusion structure of leaf power classes
- Maximal determinants of combinatorial matrices
- Total coloring of rooted path graphs
- Revising Johnson's table for the 21st century
- New results on pairwise compatibility graphs
- Linear-time algorithms for tree root problems
- On graphs that are not PCGs
- On the pairwise compatibility property of some superclasses of threshold graphs
- Pairwise compatibility graphs: a survey
- Parameterized leaf power recognition via embedding into graph products
- A survey on pairwise compatibility graphs
- Fast diameter computation within split graphs
- Ptolemaic Graphs and Interval Graphs Are Leaf Powers
- Recognition of linear and star variants of leaf powers is in P
- Recognizing k -Leaf Powers in Polynomial Time, for Constant k
- Boxicity of leaf powers
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Computing optimal leaf roots of chordal cographs in linear time
- Comparing width parameters on graph classes
- Lower bounds for leaf rank of leaf powers
- k-leaf powers cannot be characterized by a finite set of forbidden induced subgraphs for k 5
- Parameterized leaf power recognition via embedding into graph products
- Strictly chordal graphs are leaf powers
This page was built for publication: Rooted directed path graphs are leaf powers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q965972)
