New results on Ptolemaic graphs

DOI10.1016/j.dam.2014.03.024zbMath1321.05168OpenAlexW2019501411MaRDI QIDQ499349

Christina Fraga Esteves Maciel Waga, Lilian Markenzon

Publication date: 30 September 2015

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

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

zbMATH Keywords

AC graphblock duplicate graphlaminar chordal graphminimal vertex separatorPtolemaic graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (6)

The scattering number of strictly chordal graphs: linear time determination ⋮ Ptolemaic and planar cover-incomparability graphs ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Toughness and Hamiltonicity of strictly chordal graphs ⋮ Strictly chordal graphs: structural properties and integer Laplacian eigenvalues ⋮ Non-inclusion and other subclasses of chordal graphs

Cites Work

• Unnamed Item
• Reduced clique graphs of chordal graphs
• The efficiency of AC graphs
• On rigid circuit graphs
• Strictly chordal graphs are leaf powers
• Laminar structure of ptolemaic graphs with applications
• Distance-hereditary graphs
• Block duplicate graphs and a hierarchy of chordal graphs
• Algorithmic graph theory and perfect graphs
• One-phase algorithm for the determination of minimal vertex separators of chordal graphs
• A characterization of ptolemaic graphs
• Algorithms and Computation

This page was built for publication: New results on Ptolemaic graphs