Orientation distance graphs

For two nonisomorphic orientations D and D ′ of a graph G , the orientation distance d o ( D , D ′) between D and D ′ is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D ′. The orientation distance graph o ( G ) of G has the set ( G ) of pairwise nonisomorphic orientations of G as its vertex set and two vertices D and D ′ of 0 ( G ) are adjacent if and only if d o ( D , D ′)  =  1. For a nonempty subset S of ( G ), the orientation distance graph 0 ( S ) of S is the induced subgraph 〈 S 〉 of o ( G ). A graph H is an orientation distance graph if there exists a graph G and a set S ⊆ ( G ) such that o ( S ) is isomorphic to H . In this case, H is said to be an orientation distance graph with respect to G . This paper deals primarily with orientation distance graphs with respect to paths. For every integer n  ≥ 4, it is shown that o ( P n ) is Hamiltonian if and only if n is even. Also, the orientation distance graph of a path of odd order is bipartite. Furthermore, every tree is an orientation distance graph with respect to some path, as is every cycle, and for n  ≥ 3 the clique number of o ( P n ) is 2 if n is odd and is 3 otherwise. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 230–241, 2001