首页 | 本学科首页   官方微博 | 高级检索  
     


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 View the MathML source (View the MathML source) 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 View the MathML source. We show that a connected graph G is fully orientable if View the MathML source. 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号