Full Orientability of the Square of a Cycle

Abstract

Let $D$ be an acyclic orientation of a simple graph $G$. An arc of $D$ is called dependent if its reversal creates a directed cycle. Let $d(D)$ denote the number of dependent arcs in $D$. Define $d_{min}(G)$ ($d_{max}(G)$) to be the minimum (maximum) number of $d(D)$ over all acyclic orientations $D$ of $G$. We call $G$ fully orientable if $G$ has an acyclic orientation with exactly $k$ dependent arcs for every $k$ satisfying $d_{min}(G)\le k\le d_{max}(G)$. In this paper, we prove that the square of a cycle $C_n$ is fully orientable except for $n=6$.