Full orientability of graphs with at most one dependent arc |
| |
Authors: | Hsin-Hao Lai Li-Da Tong |
| |
Affiliation: | a Institute of Mathematics, Academia Sinica, Nankang, Taipei 115, Taiwan b Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung 804, Taiwan |
| |
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 () denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of G. We call Gfully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying . We show that a connected graph G is fully orientable if . 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]. |
| |
Keywords: | Acyclic orientation Dependent arc Full orientability Source-reversal Canonical decomposition |
本文献已被 ScienceDirect 等数据库收录! |
|