LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
type: Item
instance of: scholarly article
title: LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
zbMATH Open document ID: 0940.05024
DOI: 10.1016/S0166-218X(99)00157-2
author: Feodor F. Dragan
author: Falk Nicolai
published in: Discrete Applied Mathematics
publication date: 2000-07-16T00:00:00Z
review text: A graph \(G=(V,E)\) is distance-hereditary if it is connected and every induced path in \(G\) is isometric, i.e., for every connected induced subgraph \(H=(W,F)\) we have \(d_H(u,v) = d_G(u,v)\) for all vertices \(u,v \in W\). In the \(k\)th power \(G^k = (V,E^k)\) of \(G\) two vertices \(u\) and \(v\) are adjacent whenever \(d_G(u,v) \leq k\). All even powers of distance-hereditary graphs are chordal, and all odd powers are HHD-free; see \textit{H.-J. Bandelt, A. Henkmann}, and \textit{F. Nicolai} [Discrete Math. 145, No. 1-3, 37-60 (1995; Zbl 0838.05045)]. The authors prove an extension of this result dealing with common dismantling schemes provided by Lexicographic Breadth-First Search (LexBFS): Every LexBFS-ordering of a distance-hereditary graph \(G\) is both a perfect elimination ordering of all even powers of \(G\) and a semi-simplicial elimination ordering of all powers of \(G\); see \textit{B. Jamison} and \textit{S. Olariu} [Adv. Appl. Math. 9, No. 3, 364-376 (1988; Zbl 0684.05020)] for semi-simplicial elimination and \textit{F. F. Dragan, F. Nicolai}, and \textit{A. Brandstädt} [Int. J. Comput. Math. 69, No. 3-4, 217-242 (1998)] and \textit{F. F. Dragan} and \textit{F. Nicolai} [Int. J. Comput. Math. 71, No. 1, 35-56 (1999; Zbl 0934.05110)] for related results on HHD-free graphs. One forbidden subgraph characterizes the class of all distance-hereditary graphs \(G\) such that every LexBFS-ordering of \(G\) is a perfect elimination ordering of all powers of \(G\). Moreover, the diameter and a diametral pair of a distance-hereditary graph can be computed in linear time.
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1395031
zbMATH Keywords: distance-hereditary graph
zbMATH Keywords: lexicographic breadth-first-search
zbMATH Keywords: perfect elimination ordering
zbMATH Keywords: metric power
zbMATH Keywords: diameter
zbMATH Keywords: linear time algorithm
MaRDI profile type: Publication
cites work: Powers of distance-hereditary graphs
cites work: Distance-hereditary graphs
cites work: Pseudo-modular graphs
cites work: Perfect elimination orderings of chordal powers of graphs
cites work: LexBFS-orderings and powers of chordal graphs
cites work: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
cites work: Dominating cliques in distance-hereditary graphs
cites work: Convexity and HHD-Free Graphs
cites work: Q4272121
cites work: Q3222876
cites work: Q3328583
cites work: Completely separable graphs
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: On the semi-perfect elimination
cites work: Some aspects of the semi-perfect elimination
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
description: scientific article; zbMATH DE number 1395031