正则多部竞赛图中任意弧的所有长度的外路
多部竞赛图$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圈
