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
Pages :
4
From page :
2969
To page :
2972
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
Serial Year :
2009
Journal title :
Discrete Applied Mathematics
Record number :
887231
Link To Document :
بازگشت