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

For an undirected graph G the kth power Gk of G is the graph with the same 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 distance-hereditary graph is both a common perfect elimination ordering of all even powers and a common semi-simplicial ordering of all powers of this graph. Moreover, we characterize those distance-hereditary graphs by forbidden subgraphs for which every LexBFS-ordering of the graph is a common perfect elimination 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.