Powers of distance-hereditary graphs

DOI10.1016/0012-365X(94)00052-KMaRDI QIDQ1901030zbMATH OpenOpenAlexFDO

Authors Hans-Jürgen Bandelt, Anja Henkmann, Falk Nicolai

Publication date 30 May 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(94)00052-k

zbMATH Keywords

\(m\)-fanchordal graphdistance-hereditary graphsHelly numberpower graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Review text

Powers of graphs that belong to several classes have been studied. In this paper, the authors investigate powers of distance-hereditary graphs. A connected graph \(G\) is distance-hereditary if every induced path \(H\) of \(G\) is isometric; that is, the distance of any two vertices in \(H\) equals their distance in \(G\). For \(G\) distance-hereditary, the authors obtain two types of results about the power graph \(G^k\): (1) forbidden induced subgraphs (the house, domino, cycles with 5 or more vertices, isometric \(n\)-sun for \(n\geq 4\) are forbidden) and (2) distance conditions (for example, the 4-point distance condition satisfied by distance-hereditary graphs can be relaxed). The authors devote a section to the occurrence in \(G^k\) of a particular graph---the \(m\)-fan.

Recommendations

• On an extension of distance hereditary graphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• On an extension of distance-hereditary graphs
• Distance-hereditary and strongly distance-hereditary graphs
• Distance-hereditary graphs

Cites work

• A Characterization of Certain Ptolemaic Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A characterization of ptolemaic graphs
• A Classification of Reflexive Graphs: The use of “Holes”
• Clique graphs and Helly graphs
• Completely separable graphs
• Distance-hereditary graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Distances in cocomparability graphs and their powers
• Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
• scientific article; zbMATH DE number 3889566 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4045800 (Why is no real title available?)
• scientific article; zbMATH DE number 4077265 (Why is no real title available?)
• scientific article; zbMATH DE number 165077 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 867678 (Why is no real title available?)
• scientific article; zbMATH DE number 4189782 (Why is no real title available?)
• On metric properties of certain clique graphs
• On powers and centers of chordal graphs
• Pseudo-modular graphs
• Star-cutsets and perfect graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• The square of a chordal graph
• Vertex-to-vertex pursuit in a graph
• Weakly triangulated graphs

Cited in

(15)

• Reconstruction of distance hereditary 2-connected graphs
• Perfect elimination orderings of chordal powers of graphs
• Hyperbolic bridged graphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Injective hulls of various graph classes
• On the Galois Lattice of Bipartite Distance Hereditary Graphs
• On the hyperbolicity of bipartite graphs and intersection graphs
• scientific article; zbMATH DE number 4063145 (Why is no real title available?)
• Finding clubs in graph classes
• Lexbfs-orderings and powers of hhd-free graphs^∗
• Powers of hhd-free graphs^∗
• Dominating cliques in distance-hereditary graphs
• Simplicial Powers of Graphs
• Succinct data structures for bounded clique-width graphs
• LexBFS-orderings and powers of graphs

This page was built for publication: Powers of distance-hereditary graphs

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