Full orientability of graphs with at most one dependent arc
Suppose that D D is an acyclic orientation of a graph G G . An arc of D D is dependent  if its reversal creates a directed cycle. Let d min ( G ) ( d max ( G ) ) denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of G G . We call G G fully orientable  if G G has an acyclic orientation with exactly d d dependent arcs for every d d satisfying d min ( G ) ? d ? d max ( G ) . We show that a connected graph G G is fully orientable if d min ( G ) ? 1 . This generalizes the main result in Fisher etal.[D.C. Fisher, K. Fraughnaugh, L. Langley, D.B. West, The number of dependent arcs in an acyclic orientation, J. Combin. Theory Ser. B 71 (1997) 7378].
full orientability dependent arc acyclic orientation source-reversal canonical decomposition