正则多部竞赛图中任意弧的所有长度的外路  

Outpaths of all length of an arc in regular multipartite tournaments

作　　者：郭巧萍[1] 崔丽楠[1] 

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

出　　处：《高校应用数学学报（A辑）》2014年第3期288-294,共7页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(11201273;61202365;61202017);山西省青年科技基金(2011021004);山西省回国人员留学基金(2013-017)

摘　　要：多部竞赛图D中弧x_1x_2的一条(l-1)一外路是指起始于x_1x_2的长为l-1的路x_1x_2…x_1,其中要么x_1与x_1同部,要么x_1控制x_1.特别地,当l=|V(D)|且x_1控制x_1时,x_1x_2…x_lx_1是一个通过弧x_1x_2的Hamilton.Guo(Discrete Appl.Math.95(1999)273-277)证明了一个正则c-部(c≥3)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,c}.作为一个推广,该文证明了一个正则c-部(c≥5)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,|V(D)|}.进一步,使用路收缩技巧,下面一个结果也被证明:D是一个正则c-部(c≥8)竞赛图,且每个部集包含两个顶点,则D的每条弧被包含在一个Hamilton圈中.这个结果部分地支持了Volkmann和Yeo(Discrete Math.281(2004)267-276)提出的猜想:正则多部竞赛图的每条孤都包含在一个Hamilton圈中.An （l - 1）-outpath of an arc xtx1 in a multipartite tournament is a path x1x2… xl of length l - 1 starting with xtx1, such that either x1 and x1 are in the same partite set or x1 dominates x1. Specially,x1x2...xlx1 is a Hamilton cycle when l = ｜V（D）｜ and x1 dominates x1. Guo （Discrete Appl Math 95 （1999） 273-277） proved that every arc of a regular c-partite tournament with c 〉 3 has a （k - 1）-outpath for each k ∈ {3, 4,... , c}. As a generalization, this paper proves that every arc in a regular c-partite tournament with c ≥ 5 has a （k - 1）-outpath for each k ∈ {3,4,... , ｜V（D）｜}. Furthermore, using the method of path-contracting, the paper also proves the following result： Let D be a regular c-partite tournament. If c ≥ 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.

关 键 词：正则多部竞赛图 外路 HAMILTON 

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