LexBFS-orderings and powers of chordal graphs (Q1363684)

Two vertices of the \(k\)th power of a graph \(G\) are adjacent if and only if their distance in \(G\) does not exceed \(k\). The lexicographic breadth-first-search (LexBFS) [see \textit{D. J. Rose}, \textit{R. E. Tarjan} and \textit{G. S. Lueker}, SIAM J. Comput. 5, 266-283 (1976; Zbl 0353.65019)] and the maximum cardinality search (MCS) [see \textit{R. E. Tarjan} and \textit{M. Yannakakis}, SIAM J. Comput. 13, 566-579 (1984; Zbl 0545.68062)] give a perfect elimination ordering of a chordal graph in linear time [see \textit{M. C. Golombic}, Algorithmic graph theory and perfect graphs (1980; Zbl 0541.05054)]. In this paper the authors prove that the LexBFS-ordering of a chordal graph is a common perfect elimination ordering of all odd powers of this graph. Also results concerning even powers and MCS are presented.