Perfect elimination orderings of chordal powers of graphs

AbstractLet G = (V,E) be a finite undirected connected graph. We show that there is a common perfect elimination ordering of all powers of G which represent chordal graphs. Consequently, if G and all of its powers are chordal then all these graphs admit a common perfect elimination ordering. Such an ordering can be computed in O(|V| · |E|) time using a generalization of the Tarjan and Yannakakis' Maximum Cardinality Search