Please wait a minute...
高校应用数学学报
Applied Mathematics A Journal of Chinese Universities  2017, Vol. 32 Issue (4): 487-492    DOI:
    
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
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

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     
Received: 01 April 2016      Published: 01 December 2018
CLC:  O157.5  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
LI Rui-juan
HAN Ting-ting
Cite this article:

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.

URL:

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


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

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路 
[1] WANG Zhan-qing, WANG Li-gong, MEI Ruo-xing, ZHAI Ruo-nan, DONG Zhan-peng. Two kinds of bicyclic graphs are determined by their Laplacian spectra[J]. Applied Mathematics A Journal of Chinese Universities, 2016, 31(1): 73-82.
[2] WU Bao-feng, PANG Lin-lin, SHEN Fu-qiang. On the least signless Laplacian eigenvalue of graphs[J]. Applied Mathematics A Journal of Chinese Universities, 2016, 31(1): 83-89.
[3] HE Chang-xiang, LIU Shi-qiong. The star matching number and (signless) Laplacian eigenvalues[J]. Applied Mathematics A Journal of Chinese Universities, 2015, 30(3): 333-339.
[4] GUO Qiao-ping, CUI Li-nan. Outpaths of all length of an arc in regular multipartite tournaments[J]. Applied Mathematics A Journal of Chinese Universities, 2014, 29(3): 288-294.