LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem

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.