Title of article :
Full orientability of graphs with at most one dependent arc
Author/Authors :
Hsin-Hao Lai، نويسنده , , Ko-Wei Lih، نويسنده , , Li-Da Tong، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Abstract :
Suppose that image is an acyclic orientation of a graph image. An arc of image is dependent if its reversal creates a directed cycle. Let image (image) denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of image. We call image fully orientable if image has an acyclic orientation with exactly image dependent arcs for every image satisfying image. We show that a connected graph image is fully orientable if image. 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 :
Source-reversal , Full orientability , Dependent arc , Acyclic orientation , Canonical decomposition
Journal title :
Discrete Applied Mathematics
Journal title :
Discrete Applied Mathematics