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

摘要：

多部竞赛图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