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.