Powers of distance-hereditary graphs
type: Item
instance of: scholarly article
title: Powers of distance-hereditary graphs
zbMATH Open document ID: 0838.05045
DOI: 10.1016/0012-365X(94)00052-K
author: Hans-Jürgen Bandelt
author: Anja Henkmann
author: Falk Nicolai
published in: Discrete Mathematics
publication date: 1996-05-30T00:00:00Z
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.
reviewed by: Norman F. Quimpo
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 810254
zbMATH Keywords: chordal graph
zbMATH Keywords: Helly number
zbMATH Keywords: distance-hereditary graphs
zbMATH Keywords: power graph
zbMATH Keywords: \(m\)-fan
MaRDI profile type: Publication
cites work: Distance-hereditary graphs
cites work: Pseudo-modular graphs
cites work: Q4873790
cites work: Clique graphs and Helly graphs
cites work: Q4099676
cites work: Q5753991
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: A Characterization of Certain Ptolemaic Graphs
cites work: Star-cutsets and perfect graphs
cites work: Q3808118
cites work: Distances in cocomparability graphs and their powers
cites work: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
cites work: Q3222876
cites work: Q3328583
cites work: Completely separable graphs
cites work: The square of a chordal graph
cites work: Weakly triangulated graphs
cites work: Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: On metric properties of certain clique graphs
cites work: A characterization of ptolemaic graphs
cites work: A Classification of Reflexive Graphs: The use of “Holes”
cites work: On powers and centers of chordal graphs
cites work: Vertex-to-vertex pursuit in a graph
cites work: Q3783331
cites work: Q4032992
full work available at URL: 0012-365x(94)00052-k
OpenAlex ID: W2002776156
description: scientific article; zbMATH DE number 810254