Rooted directed path graphs are leaf powers

DOI10.1016/J.DISC.2009.10.006MaRDI QIDQ965972zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Christian Hundt, F. Mancini, 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

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

Recommendations

• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• On (k,ℓ)-Leaf Powers
• Characterising \((k,\ell )\)-leaf powers
• On k- Versus (k + 1)-Leaf Powers
• Structure and linear time recognition of 3-leaf powers

Cites work

• scientific article; zbMATH DE number 3839362 (Why is no real title available?)
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A Characterization of Comparability Graphs and of Interval Graphs
• A Class of Balanced Matrices Arising from Location Problems
• A characterization of ptolemaic graphs
• 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
• NeST graphs
• Neighborhood subtree tolerance 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

Cited in

(21)

• Linear-time algorithms for tree root problems
• Comparing width parameters on graph classes
• A survey on pairwise compatibility graphs
• Boxicity of leaf powers
• On graphs that are not PCGs
• Recognition of linear and star variants of leaf powers is in P
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• Pairwise compatibility graphs: a survey
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• Lower bounds for leaf rank of leaf powers
• Computing optimal leaf roots of chordal cographs in linear time
• Maximal determinants of combinatorial matrices
• New results on pairwise compatibility graphs
• Parameterized leaf power recognition via embedding into graph products
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Fast diameter computation within split graphs
• Parameterized leaf power recognition via embedding into graph products
• On the pairwise compatibility property of some superclasses of threshold graphs
• Strictly chordal graphs are leaf powers
• Total coloring of rooted path graphs
• Revising Johnson's table for the 21st century

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)