Rooted directed path graphs are leaf powers

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

zbMATH Keywords

rooted directed path graphsstrongly chordal graphsleaf powersleaf roots(Unit) interval graphsfixed tolerance nest graphsgraph class inclusionsptolemaic graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

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