LexBFS-orderings and powers of chordal graphs 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 any LexBFS-ordering of a chordal graph is a common perfect elimination ordering of all odd powers of this graph. Moreover, we characterize those chordal graphs by forbidden isometric subgraphs for which any LexBFS-ordering of the graph is a common perfect elimination ordering of all powers. For MCS-orderings of chordal graphs the situation is worse: even for trees MCS does not give a common perfect elimination ordering of powers.