ON DISTANCE-PRESERVING AND DOMINATION ELIMINATION ORDERINGS

A distance-preserving elimination ordering of a graph G is a linear or dering upsilon(1,) upsilon(2),..., upsilon(n) of the vertices such tha t each subgraph G(i) = G(upsilon(1),..., upsilon(i)); i < n, is an iso metric 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 gr eater than or equal to 5, and the bipyramids bipyr(C-m), m greater tha n or equal to 6, as an isometric subgraph, then any ordering produced by the lexicographic breadth-first search is a domination elimination ordering (i.e., every vertex vi is dominated by some vertex upsilon(j) ,j < i, or, in other words, every vertex upsilon(k); k < i, adjacent to upsilon(i) is also adjacent to upsilon(j)).