LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem (Q1962066): Difference between revisions

A graph \(G=(V,E)\) is distance-hereditary if it is connected and every induced path in \(G\) is isometric, i.e., for every connected induced subgraph \(H=(W,F)\) we have \(d_H(u,v) = d_G(u,v)\) for all vertices \(u,v \in W\). In the \(k\)th power \(G^k = (V,E^k)\) of \(G\) two vertices \(u\) and \(v\) are adjacent whenever \(d_G(u,v) \leq k\). All even powers of distance-hereditary graphs are chordal, and all odd powers are HHD-free; see \textit{H.-J. Bandelt, A. Henkmann}, and \textit{F. Nicolai} [Discrete Math. 145, No. 1-3, 37-60 (1995; Zbl 0838.05045)]. The authors prove an extension of this result dealing with common dismantling schemes provided by Lexicographic Breadth-First Search (LexBFS): Every LexBFS-ordering of a distance-hereditary graph \(G\) is both a perfect elimination ordering of all even powers of \(G\) and a semi-simplicial elimination ordering of all powers of \(G\); see \textit{B. Jamison} and \textit{S. Olariu} [Adv. Appl. Math. 9, No. 3, 364-376 (1988; Zbl 0684.05020)] for semi-simplicial elimination and \textit{F. F. Dragan, F. Nicolai}, and \textit{A. Brandstädt} [Int. J. Comput. Math. 69, No. 3-4, 217-242 (1998)] and \textit{F. F. Dragan} and \textit{F. Nicolai} [Int. J. Comput. Math. 71, No. 1, 35-56 (1999; Zbl 0934.05110)] for related results on HHD-free graphs. One forbidden subgraph characterizes the class of all distance-hereditary graphs \(G\) such that every LexBFS-ordering of \(G\) is a perfect elimination ordering of all powers of \(G\). Moreover, the diameter and a diametral pair of a distance-hereditary graph can be computed in linear time.