Lexbfs-orderings and powers of hhd-free graphs ^∗

First author supported by VW, Project No. I/69041 and by DFG, second author supported by DFG

Abstract

The k-th power of a graph G is the graph with the same vertex set as G where two vertices are adjacent iff their distance in G is at most k. We investigate LexBFS-orderings of HHD-free graphsi.e., the graphs where each cycle of length at least five has two chords, with respect to their powers, It is well-known that any LexBFS-ordering of a HHD-free graph is a so-called semisimplicial ordering. We show, that any LexBFS-ordering of a HHD-free graph is a common semisimplicial ordering of all its odd powers. Furthermore, we characterize those HHD-free graphs by forbidden subgraphs for which any LexBFS-ordering of the initial graph is a common perfect elimination ordering of all odd or even powers

Keywords:

• HHD-free graphs
• LexBFS-ordering
• k-th power

[email protected]

First author supported by VW, Project No. I/69041 and by DFG, second author supported by DFG

[email protected]

First author supported by VW, Project No. I/69041 and by DFG, second author supported by DFG

Notes

[email protected]

First author supported by VW, Project No. I/69041 and by DFG, second author supported by DFG