Name
Abstract | ||
|---|---|---|
Suppose that D is an acyclic orientation of a graph G. An arc of D is dependent if its reversal creates a directed cycle. Let dmin(G) (dmax(G)) denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of G. We call G fully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying dmin(G)⩽d⩽dmax(G). We show that a connected graph G is fully orientable if dmin(G)⩽1. This generalizes the main result in Fisher et al. [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) 73–78]. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.dam.2009.04.013 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Acyclic orientation,Dependent arc,Full orientability,Source-reversal,Canonical decomposition | Discrete mathematics,Graph,Combinatorics,Arc (geometry),Orientability,Decomposition method (constraint satisfaction),Directed acyclic graph,Connectivity,Canonical decomposition,Mathematics,Acyclic orientation | Journal |
Volume | Issue | ISSN |
157 | 13 | 0166-218X |
Citations | PageRank | References |
1 | 0.37 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsin-Hao Lai | 1 | 13 | 3.19 |
| Ko-wei Lih | 2 | 529 | 58.80 |
| Li-da Tong | 3 | 46 | 12.49 |