On Distance-Preserving and Domination Elimination Orderings
Victor D. Chepoi · SIAM Journal on Discrete Mathematics · 1998
A distance-preserving elimination ordering of a graph G is a linear ordering v 1 ,v 2,..., v n of the vertices such that each subgraph G i =G(v 1 ,...,v i ),i < n, is an isometric subgraph of G. We prove that the ordering of the vertices of a pseudo-modular or a house-free weakly modular graph G produced by the breadth-first search is distance preserving. We specify this result by showing that if, in addition, G does not contain the cycles C n , n\geq 5, and the bipyramids $bipyr(C_m), m\geq 6,$ as an isometric subgraph, then any ordering produced by the lexicographic breadth-first search is a domination elimination ordering (i.e., every vertex v i is dominated by some vertex v j , j < i, or, in other words, every vertex v k , k < i, adjacent to v i is also adjacent to v j ).