正圆有向图中的弧不相交的Hamilton路和圈  

Arc-disjoint Hamiltonian cycles and paths in positive-round digraphs

作　　者：李瑞娟[1] 韩婷婷[1] LI Rui-juan;HAN Ting-ting(School of Math. Sci., Shanxi Univ., Taiyuan 030006, China)

机构地区：[1]山西大学数学科学学院,山西太原030006

出　　处：《高校应用数学学报（A辑）》2017年第4期487-492,共6页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(11401353);山西省自然科学基金(2016011005)

摘　　要：2012年,Bang-Jensen和Huang(J.Combin.Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想.主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈,并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路,使得它们两两弧不相交.由于任意圆有向图一定是正圆有向图,所得结论可以推广到圆有向图中.又由于圆有向图是局部竞赛图的子图类,因此所得结论说明对局部竞赛图的子图类――圆有向图,Bang-Jensen和Huang的猜想成立.In2012,Bang-Jensen and Huang(J.Combin.Theory Ser.B.2012,102:701-714)proved that every2-arc-strong locally semicomplete digraph has two arc-disjoint strongly connected spanning subdigraphs,and conjectured that every3-strong local tournament has two arc-disjoint hamil-tonian cycles.In this paper,the arc-disjoint hamiltonian paths and cycles in positive-round digraphs are discussed,and the following results are proved:every3-arc-strong positive-round digraph contains two arc-disjoint hamiltonian cycles and every4-arc-strong positive-round digraph contains one hamil-tonian 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.

关 键 词：正圆有向图 弧不相交 HAMILTON圈 HAMILTON路 

分 类 号：O157.5[理学—数学]