高校应用数学学报A辑
高校應用數學學報A輯
고교응용수학학보A집
APPLIED MATHEMATICS A JOURNAL OF CHINESE UNIVERSITIES
2014年
3期
288-294
,共7页
正则多部竞赛图%外路%Hamilton圈
正則多部競賽圖%外路%Hamilton圈
정칙다부경새도%외로%Hamilton권
regular multipartite tournaments%outpath%Hamilton cycle
多部竞赛图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圈中.
多部競賽圖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圈中.
다부경새도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권중.
