On Distance-Preserving and Domination Elimination Orderings

DOI10.1137/S0895480195291230MaRDI QIDQ4210215zbMATH OpenFDO

Authors Victor Chepoi

Publication date 21 September 1998

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480195291230

zbMATH Keywords

breadth-first searchcharacterizationdistance-preserving orderingdomination elimination orderingdomination graphshouse-free weakly modular graphslexicographic breadth-first searchpseudo-peakless functions

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10)

Review text

Let \(G= (V,E)\) be a finite undirected graph. The distance between two vertices in \(G\) is the length of a shortest path between them. An induced subgraph \(G(U)\) of \(G\) for \(U\subseteq V\) is isometric if the distances in \(G(U)\) are the same as in \(G\). A linear ordering \((v_1,\dots, v_n)\) of the vertices of \(G\) is a distance-preserving ordering if, for all \(i\), \(1\leq i< n\), the induced subgraph \(G_i=G(\{v_1,\dots, v_i\})\) is isometric. This paper shows that for two graph classes, namely pseudo-modular and house-free weakly modular graphs, every vertex ordering produced by breadth-first search (BFS) is distance-preserving. This leads to a characterization of hereditary weakly modular graphs in terms of distance-preserving BFS orderings for every isometric subgraph. An important tool for these results is the notion of pseudo-peakless functions on graphs studied by the same author in an earlier paper. For house-free graphs \(G\), the following characterization is given: \(G\) contains no chordless cycle \(C_n\), \(n\geq 5\), and no bipyramid \(\text{bipyr}(C_m)\), \(m\geq 6\), as isometric subgraphs if and only if for each isometric subgraph of \(G\), every of its vertex orderings produced by lexicographic breadth-first search (LexBFS) is a domination elimination ordering. These results give new insights into classic concepts such as BFS and LexBFS on important graph classes such as pseudo- and weakly modular graphs introduced and studied by Bandelt et al. as well as domination graphs and (house, hole)-free graphs introduced and studied by Dahlhaus et al.

Recommendations

• On distance-preserving elimination orderings in graphs: complexity and algorithms
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• LexBFS-orderings and powers of chordal graphs

Cited in

(17)

• A witness version of the cops and robber game
• On distance-preserving elimination orderings in graphs: complexity and algorithms
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Graphs of some CAT(0) complexes
• Ambush cops and robbers
• Medians in median graphs and their cube complexes in linear time
• Perfect elimination orderings for symmetric matrices
• Tandem-win graphs
• Weakly Modular Graphs and Nonpositive Curvature
• Characterizations of k-copwin graphs
• Graphs with \(G^p\)-connected medians
• First-order logic axiomatization of metric graph theory
• The complexity of growing a graph
• Medians in median graphs and their cube complexes in linear time
• Cops and robber with decoys
• On distance preserving and sequentially distance preserving graphs
• Edge critical cops and robber

This page was built for publication: On Distance-Preserving and Domination Elimination Orderings

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