| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420363 | Discrete Applied Mathematics | 2006 | 7 Pages |
Abstract
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)dmin(G) (dmax(G)dmax(G)) to be the minimum (maximum) number of d(D)d(D) over all acyclic orientations D of G . We determine dmin(G)dmin(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)dmin(G)⩽k⩽dmax(G).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ko-Wei Lih, Chen-Ying Lin, Li-Da Tong,