Please wait a minute...
高校应用数学学报
高校应用数学学报  2014, Vol. 29 Issue (3): 288-294    
    
正则多部竞赛图中任意弧的所有长度的外路
郭巧萍, 崔丽楠
山西大学 数学科学学院, 山西太原 030006
Outpaths of all length of an arc in regular multipartite tournaments
GUO Qiao-ping, CUI Li-nan
School of Mathematical Sciences, Shanxi University, Taiyuan 030006, China
 全文: PDF 
摘要： 多部竞赛图$D$中弧$x_1x_2$的一条$(l-1)$-外路是指起始于$x_1x_2$的长为$l-1$的路$x_1x_2\cdots x_l$, 其中要么$x_l$与$x_1$同部, 要么$x_l$ 控制$x_1$. 特别地, 当$l=|V(D)|$且$x_l$控制$x_1$时, $x_1x_2\cdots x_lx_1$ 是一个通过弧$x_1x_2$ 的Hamilton圈. Guo (Discrete Appl. Math. 95 (1999) 273-277) 证明了一个正则$c$-部($c\geq 3$) 竞赛图中的每条弧都有一个$(k-1)$-外路, 其中$k\in\{3, 4, \cdots, c\}$. 作为一个推广, 该文证明了一个正则$c$-部($c\geq 5$) 竞赛图中的每条弧都有一个$(k-1)$-外路, 其中$k\in\{3, 4, \cdots, |V(D)|\}$. 进一步, 使用路收缩技巧, 下面一个结果也被证明: $D$是一个正则$c$-部($c\geq 8$)竞赛图, 且每个部集包含两个顶点, 则$D$的每条弧被包含在一个Hamilton 圈中. 这个结果部分地支持了Volkmann 和Yeo (Discrete Math. 281 (2004) 267-276)提出的猜想: 正则多部竞赛图的每条弧都包含在一个Hamilton 圈中.
关键词： 正则多部竞赛图;  外路;  Hamilton圈    
Abstract: An $(l-1)$-outpath of an arc $x_1x_2$ in a multipartite tournament is a path $x_1x_2\cdots x_l$ of length $l-1$ starting with $x_1x_2$, such that either $x_l$ and $x_1$ are in the same partite set or $x_l$ dominates $x_1$. Specially, $x_1x_2\cdots x_lx_1$ is a Hamilton cycle when $l=|V(D)|$ and $x_l$ dominates $x_1$. Guo (Discrete Appl Math 95 (1999) 273-277) proved that every arc of a regular $c$-partite tournament with $c\geq 3$ has a $(k-1)$-outpath for each $k\in \{3, 4, \cdots, c\}$. As a generalization, the paper proves that every arc in a regular $c$-partite tournament with $c\geq 5$ has a $(k-1)$-outpath for each $k\in \{3, 4, \cdots, |V(D)|\}$ in this article. Furthermore, using the method of path-contracting, the paper also proves the following result: Let $D$ be a regular $c$-partite tournament. If $c\geq 8$ and there are two vertices in every partite set, then each arc in $D$ is contained in a Hamilton cycle. This result gives a partial support to the conjecture posed by Volkmann and Yeo (Discrete Math 281 (2004) 267-276) that each arc of a regular multipartite tournament is contained in a Hamilton cycle.
Key words: regular multipartite tournaments    outpath    Hamilton cycle
收稿日期: 2014-04-02 出版日期: 2018-06-10
CLC:  O157.5  
基金资助: 国家自然科学基金(11201273; 61202365; 61202017); 山西省青年科技基金(2011021004); 山西省回国人员留学基金(2013-017)
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
郭巧萍
崔丽楠

引用本文:

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

GUO Qiao-ping, CUI Li-nan. Outpaths of all length of an arc in regular multipartite tournaments. Applied Mathematics A Journal of Chinese Universities, 2014, 29(3): 288-294.

链接本文:

http://www.zjujournals.com/amjcua/CN/    或    http://www.zjujournals.com/amjcua/CN/Y2014/V29/I3/288

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