On an interpolation property of outerplanar graphs
Let D be an acyclic orientation of a graph G. An arc of D is said to be dependent  if its reversal creates a directed cycle. Let d(D) d ( D ) denote the number of dependent arcs in D . Define dmin(G) d min ( G ) (dmax(G) d max ( G ) ) to be the minimum (maximum) number of d(D) d ( D ) over all acyclic orientations D of G . We determine dmin(G) d min ( G ) for an outerplanar graph G and prove that G has an acyclic orientation with exactly k  dependent arcs if dmin(G)?k?dmax(G) d min ( G ) ? k ? d max ( G ) .
interpolation property outerplanar graph acyclic orientation dependent arc