Please wait a minute...
高校应用数学学报
高校应用数学学报  2017, Vol. 32 Issue (4): 487-492    
    
正圆有向图中的弧不相交的Hamilton路和圈
李瑞娟, 韩婷婷
山西大学数学科学学院, 山西太原030006
Arc-disjoint Hamiltonian cycles and paths in positive-round digraphs#br#
LI Rui-juan, HAN Ting-ting
School of Math. Sci., Shanxi Univ., Taiyuan 030006, China
 全文: PDF 
摘要： 2012年, Bang-Jensen和Huang(\emph{J. Combin. Theory Ser. B}. 2012, {\bf 102:} 701-714)证明了$2$-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当$D$不是偶圈的二次幂, 并提出了任意$3$-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想. 主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈, 并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路, 使得它们两两弧不相交. 由于任意圆有向图一定是正圆有向图, 所得结论可以推广到圆有向图中. 又由于圆有向图是局部竞赛图的子图类, 因此所得结论说明对局部竞赛图的子图类——圆有向图, Bang-Jensen和Huang的猜想成立.
关键词： 正圆有向图;  弧不相交;  Hamilton圈;  Hamilton路    
Abstract: In 2012, Bang-Jensen and Huang (\emph{J. Combin. Theory Ser. B}. 2012, {\noindent\bf  102}: 701-714) proved that every $2$-arc-strong locally semicomplete digraph has two arc-disjoint strongly connected spanning subdigraphs, and conjectured that every $3$-strong local tournament has two arc-disjoint hamiltonian cycles. In this paper, the arc-disjoint hamiltonian paths and cycles in positive-round digraphs are discussed, and the following results are proved: every 3-arc-strong positive-round digraph contains two arc-disjoint hamiltonian cycles and every 4-arc-strong positive-round digraph contains one hamiltonian cycle and two hamiltonian paths, such that they are arc-disjoint pairwise. A round digraph must be positive-round, thus those conclusions on positive-round digraphs can be generalized to round digraphs. Since round digraphs form the subclass of local tournaments, Bang-Jensen and Huang's conjecture holds for round digraphs which is the subclass of local tournaments.
Key words: positive-round digraph    arc-disjoint    Hamiltonian cycle    Hamiltonian path
收稿日期: 2016-04-01 出版日期: 2018-12-01
CLC:  O157.5  
基金资助: 国家自然科学基金(11401353); 山西省自然科学基金(2016011005)
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
李瑞娟
韩婷婷

引用本文:

李瑞娟, 韩婷婷. 正圆有向图中的弧不相交的Hamilton路和圈[J]. 高校应用数学学报, 2017, 32(4): 487-492.

LI Rui-juan, HAN Ting-ting. Arc-disjoint Hamiltonian cycles and paths in positive-round digraphs#br#. Applied Mathematics A Journal of Chinese Universities, 2017, 32(4): 487-492.

链接本文:

http://www.zjujournals.com/amjcua/CN/    或    http://www.zjujournals.com/amjcua/CN/Y2017/V32/I4/487

[1] 郭巧萍, 崔丽楠. 正则多部竞赛图中任意弧的所有长度的外路[J]. 高校应用数学学报, 2014, 29(3): 288-294.