Rooted directed path graphs are leaf powers
From MaRDI portal
Publication:965972
DOI10.1016/j.disc.2009.10.006zbMath1211.05051OpenAlexW2093500811MaRDI QIDQ965972
Federico Mancini, Christian Hundt, Andreas Brandstädt, Peter Wagner
Publication date: 27 April 2010
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2009.10.006
rooted directed path graphsstrongly chordal graphsleaf powersleaf roots(Unit) interval graphsfixed tolerance nest graphsgraph class inclusionsptolemaic graphs
Related Items (15)
Maximal determinants of combinatorial matrices ⋮ Pairwise Compatibility Graphs: A Survey ⋮ Towards a characterization of leaf powers by clique arrangements ⋮ New results on pairwise compatibility graphs ⋮ Recognition of linear and star variants of leaf powers is in P ⋮ Recognizing k -Leaf Powers in Polynomial Time, for Constant k ⋮ Total coloring of rooted path graphs ⋮ Parameterized Leaf Power Recognition via Embedding into Graph Products ⋮ On graphs that are not PCGs ⋮ ON THE PAIRWISE COMPATIBILITY PROPERTY OF SOME SUPERCLASSES OF THRESHOLD GRAPHS ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ Revising Johnson's table for the 21st century ⋮ A survey on pairwise compatibility graphs ⋮ Linear-time algorithms for tree root problems ⋮ Fast Diameter Computation within Split Graphs
Cites Work
- Unnamed Item
- Consecutive retrieval property -- revisited
- Structure and linear time recognition of 3-leaf powers
- Strictly chordal graphs are leaf powers
- A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
- Characterizations of strongly chordal graphs
- Distance-hereditary graphs
- NeST graphs
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- Neighborhood subtree tolerance graphs
- Tree spanners on chordal graphs: complexity and algorithms
- Some remarks about leaf roots
- Error compensation in leaf power problems
- On Graph Powers for Leaf-Labeled Trees
- A Class of Balanced Matrices Arising from Location Problems
- The 3-Steiner Root Problem
- The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
- A characterization of ptolemaic graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Ptolemaic Graphs and Interval Graphs Are Leaf Powers
- Simplicial Powers of Graphs
- On k- Versus (k + 1)-Leaf Powers
- A Characterization of Comparability Graphs and of Interval Graphs
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Rooted directed path graphs are leaf powers
