Name
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) denote the number of dependent arcs in D. Define dmin(G) (dmax(G)) to be the minimum (maximum) number of d(D) over all acyclic orientations D of G. We determine 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). |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.dam.2005.07.004 | Discrete Applied Mathematics |
Keywords | Field | DocType |
acyclic orientation,outerplanar graph,interpolation property,k dependent arc,dependent arc,acyclic orientations d,graph g. | Graph,Discrete mathematics,Outerplanar graph,Combinatorics,Interpolation,Directed acyclic graph,Mathematics,Acyclic orientation | Journal |
Volume | Issue | ISSN |
154 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
7 | 0.69 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ko-wei Lih | 1 | 529 | 58.80 |
| Chen-Ying Lin | 2 | 10 | 1.82 |
| Li-da Tong | 3 | 46 | 12.49 |