Orientation distance graphs
Gary Chartrand, David J. Erwin, Michael E. Raines, Ping Zhang · Journal of Graph Theory · 2001
For two nonisomorphic orientations D and D′ of a graph G, the orientation distance do(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 do(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(Pn) 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(Pn) is 2 if n is odd and is 3 otherwise. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 230–241, 2001