10.3969/j.issn.1000-4424.2014.03.005
正则多部竞赛图中任意弧的所有长度的外路
多部竞赛图D中孤x1 x2的一条(l-1)-外路是指起始于x1x2的长为l-1的路x1x2…xl,其中要么xl与x1同部,要么xl控制x1.特别地,当l=|V(D)|且xl控制x1时,x1 x2…xtx1是一个通过弧x1x2的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)m进一步,使用路收缩技巧,下面一个结果也被证明:D是一个正则c-部(c≥8)竞赛图,且每个部集包含两个顶点,则D的每条弧被包含在一个Hamilton圈中.这个结果部分地支持了Volkmann和Yeo(Discrete Math.281 (2004) 267-276)提出的猜想:正则多部竞赛图的每条弧都包含在一个Hamilton圈中.
正则多部竞赛图、外路、Hamilton圈
29
O157.5(代数、数论、组合理论)
国家自然科学基金11201273, 61202365, 61202017;山西省青年科技基金2011021004;山西省回国人员留学基金2013-017
2014-11-03(万方平台首次上网日期,不代表论文的发表时间)
共7页
288-294