Characterising \((k,\ell )\)-leaf powers

DOI10.1016/j.dam.2009.09.008zbMath1225.05079OpenAlexW2057773519MaRDI QIDQ968117

Andreas Brandstädt, Peter Wagner

Publication date: 5 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.09.008

zbMATH Keywords

treesblock graphsrecognition algorithmsstrictly chordal graphscharacterisations\((k,\ell)\)-leaf powers\(k\)-leaf powers

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

On basic chordal graphs and some of its subclasses ⋮ The scattering number of strictly chordal graphs: linear time determination ⋮ Pairwise Compatibility Graphs: A Survey ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ Characterizing star-PCGs ⋮ Non-inclusion and other subclasses of chordal graphs ⋮ On graphs that are not PCGs ⋮ Mim-width. III. Graph powers and generalized distance domination problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Distance-hereditary graphs
• On metric properties of certain clique graphs
• Efficient graph representations
• Linear-time recognition of circular-arc graphs
• Neighborhood subtree tolerance graphs
• A note on the metric properties of trees
• Representing a concept lattice by a graph
• Some remarks about leaf roots
• Error compensation in leaf power problems
• On Graph Powers for Leaf-Labeled Trees
• The 3-Steiner Root Problem
• On (k,ℓ)-Leaf Powers
• Leaf Powers and Their Properties: Using the Trees
• A Dynamic Programming Algorithm for Covering Problems with (Greedy) Totally Balanced Constraint Matrices
• Graph Classes: A Survey
• Structure and linear-time recognition of 4-leaf powers
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Simplicial Powers of Graphs
• On k- Versus (k + 1)-Leaf Powers
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation

This page was built for publication: Characterising \((k,\ell )\)-leaf powers