Strictly chordal graphs are leaf powers

DOI10.1016/J.JDA.2005.06.005MaRDI QIDQ866539zbMATH OpenOpenAlexFDO

Authors W. Sean Kennedy, Guohui Lin, Guiying Yan

Publication date 14 February 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2005.06.005

zbMATH Keywords

computational biologychordalphylogeny reconstructionleaf rootSteiner rootstrictly chordal

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Computational methods for problems pertaining to biology (92-08)

Recommendations

• On strongly chordal graphs that are not leaf powers
• Characterising \((k,\ell )\)-leaf powers
• On (k,ℓ)-Leaf Powers
• Rooted directed path graphs are leaf powers
• Exact leaf powers

Cites work

• scientific article; zbMATH DE number 1617253 (Why is no real title available?)
• scientific article; zbMATH DE number 2080275 (Why is no real title available?)
• Algorithms for Square Roots of Graphs
• Computing roots of graphs is hard
• Graph Classes: A Survey
• Introduction to algorithms
• On graph powers for leaf-labeled trees
• On the complexity of join dependencies
• Recent Advances in Constraints
• Tree Powers

Cited in

(27)

• Boxicity of leaf powers
• On graphs that are not PCGs
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• Simplicial powers of graphs
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• The 3-Steiner Root Problem
• Ptolemaic and planar cover-incomparability graphs
• Non-inclusion and other subclasses of chordal graphs
• Toughness and Hamiltonicity of strictly chordal graphs
• Characterising \((k,\ell )\)-leaf powers
• Strictly chordal graphs: structural properties and integer Laplacian eigenvalues
• Computing optimal leaf roots of chordal cographs in linear time
• Multicore graphs: characterization and properties
• New results on pairwise compatibility graphs
• Closest 4-leaf power is fixed-parameter tractable
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Parameterized leaf power recognition via embedding into graph products
• The complete inclusion structure of leaf power classes
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• On k- Versus (k + 1)-Leaf Powers
• Simplicial Powers of Graphs
• Parameterized leaf power recognition via embedding into graph products
• On strongly chordal graphs that are not leaf powers
• On the pairwise compatibility property of some superclasses of threshold graphs
• Rooted directed path graphs are leaf powers
• New results on Ptolemaic graphs
• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers

This page was built for publication: Strictly chordal graphs are leaf powers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866539)