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 $\cD_o(G)$ of $G$ has the set $\cO(G)$ of pairwise nonisomorphic orientations of $G$ as its vertex set and two vertices $D$ and $D'$ of $\cD_o(G)$ are adjacent if and only if $d_o(D, D')=1.$ For a nonempty subset $S$ of $\cO(G)$, the orientation distance graph $\cD_o(S)$ of $S$ is the induced subgraph $\langle{S}\rangle$ of $\cD_o(G)$. A graph $H$ is an orientation distance graph if there exists a graph $G$ and a set $S \sbe \cO(G)$ such that $\cD_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 \geq 4$, it is shown that $\cD_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 \geq 3$ the clique number of $\cD_o (P_{n})$ is 2 if $n$ is odd and is 3 otherwise.