Orientation distance graphs

For two nonisomorphic orientations D and D' of a graph G, the orientation d istance d(o)(D,D') between D and D' is the minimum number of arcs of D whos e directions must be reversed to produce an orientation isomorphic to D'. T he orientation distance graph D-o(G) of G has the set O(G) of pairwise noni somorphic orientations of G as its vertex set and two vertices D and D' of D-o(G) are adjacent if and only if d(o)(D,D') = 1. For a nonempty subset S of O(G), the orientation distance graph D-o(S) of Sis the induced subgraph (S) of D-o(G). A graph His an orientation distance graph if there exists a graph G and a set S subset of or equal to O(G) such that D-o(S) is isomorph ic to H. In this case, H is said to be an orientation distance graph with r espect to G. This paper dears primarily with orientation distance graphs wi th respect to paths. For every integer n greater than or equal to 4, it is shown that D-o(P-n) is Hamiltonian if and only if n is even. Also, the orie ntation distance graph of a path of odd order is bipartite. Furthermore, ev ery tree is an orientation distance graph with respect. to some path, as is every cycle, and for n greater than or equal to3 the clique number of D-o( P-n) is 2 if n is odd and is 3 otherwise. (C) 2001 John Wiley & Sons, Inc.