Ff. Dragan et F. Nicolai, LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem, DISCR APP M, 98(3), 2000, pp. 191-207
For an undirected graph G the kth power G(k) of G is the graph with the sam
e vertex set as G where two vertices are adjacent iff their distance is at
most k in G. In this paper we prove that every LexBFS-ordering of a distanc
e-hereditary graph is both a common perfect elimination ordering of all eve
n powers and a common semi-simplicial ordering of all powers of this graph.
Moreover, we characterize those distance-hereditary graphs by forbidden su
bgraphs for which every LexBFS-ordering of the graph is a common perfect el
imination ordering of all powers. As an application we present an algorithm
which computes the diameter and a diametral pair of vertices of a distance
-hereditary graph in linear time. (C) 2000 Elsevier Science B.V. All rights
reserved.