The minimum number of dependent arcs in С³₃k - Xu, Fengwei; Wang, Weifan; Lih, Ko-Wei (Tamsui Oxford Journal of Mathematical Sciences)
Let D be an acyclic orientation of a simple graph G. An arc is called depenedent if its reversal creates a directed cycle. Let d (D) denote the number of dependent arcs in D. Define d min (G) to be the minimum number of d (D) over all acyclic orientations D of G. Let Cn denote the cycle on n vertices. The cube С³n is the graph defined on the same vertex set of Cn such that any two distinct vertices u and v are adjacent in С³n if and only if their distance in Cn is at most 3. In this paper, we study the structure of С³₃k to determine its minimum number of dependent arcs.