Edge-Disjoint Hamilton Cycles in Regular Graphs of Large Degree
Edge-Disjoint Hamilton Cycles in Regular Graphs of Large Degree
复制标题
大次数正则图中边不相交的哈密顿循环
DOI：
10.1112/jlms/s2-19.1.13
复制
发表时间：
1979
影响因子：
1.2
通讯作者：
B. Jackson
中科院分区：
文献类型：
--
作者：
B. Jackson
本文所考虑的所有图都是简单的。对于实数x，设[x]表示小于或等于x的最大整数。我们将证明以下结果。定理1.设G是n个顶点的k-正则图，其中14^n<；2/r+L，则G含有[iqk-n+L]个边不交的哈密顿圈。对于h为整数，如果h为偶数，则定义h为零，如果h为奇数，则定义为1。纳什-威廉姆斯[5；定理3]证明了以下几点。定理2.若图G有n个最小度k的顶点，且n<；2k，则G包含[-jrzin+an+10)]个边不交的哈密顿圈。定理1表明，如果G是n个顶点的A：-正则图，且n^2k，则G包含Wr(n+3an+2)]个边不交的哈密尔顿圈。因此，我们可以通过增加一个正则性条件来增加边不相交的哈密顿圈的个数的界。Nash-Williams在文[5]中猜想，如果G满足定理2的条件，则G包含[i(n+L)]个边不相交的哈密顿圈。尽管L.Babai随后构造了反例，但Nash-Williams指出，他的猜想仍然适用于正则图[6；pp.817-818]。我们进一步猜想，如果G是n个顶点的A>；正则图，且n^2k+，则G包含[%k]个边不交的哈密尔顿圈。这个猜想类似于P.Kelly[4；p.7]提出的任何正则竞赛图都可以分解成有向哈密尔顿圈的猜想，因为这两个猜想都暗示K2m+L在某种意义上是“强可分解”成哈密尔顿圈的。我们的猜想意味着K2m+i的[i(m-L-L)]个边不相交的哈密顿圈集合可以推广到K2m+L的哈密顿分解，Kelly的猜想意味着如果K2m+1的边以这样的方式定向，即每个顶点的度和度相等，则所得到的有向图有哈密顿分解。对于任一图G，设V{G)表示G的顶点集，E(G)表示G的边集，对H，设H是G的子图，V(H)的M和N个子图设E H{M，N)表示该集合，e w(M，N)表示M的顶点与N的顶点之间的边数.进一步，设H[M]是子图…
All graphs considered in this paper are simple. For x a real number, let [x] denote the largest integer which is less than or equal to x. We shall prove the following result. THEOREM 1. Let G be a k-regular graph on n vertices, where 14 ^ n < 2/r+l. Then G contains [iQk —n + l)] edge-disjoint Hamilton cycles. For h an integer, define a h to be zero if h is even and one if h is odd. Nash-Williams [5; Theorem 3] has proved the following. THEOREM 2. / / G is a graph on n vertices with minimum degree k, and n < 2k, then G contains [-jrzin + a n +10)] edge-disjoint Hamilton cycles. Theorem 1 implies that if G is a A:-regular graph on n vertices and n ^ 2k, then G contains Wr(n + 3a n + 2)] edge-disjoint Hamilton cycles. Thus we are able to increase the bound on the number of edge-disjoint Hamilton cycles by adding a regularity condition. In [5] Nash-Williams conjectured that if G satisfies the conditions of Theorem 2, then G contains [i(n + l)] edge-disjoint Hamilton cycles. Although counterexamples were subsequently constructed by L. Babai, Nash-Williams points out that his conjecture remains open for regular graphs [6; pp. 817-818]. We conjecture further, that if G is a A>regular graph on n vertices and n^2k+\ then G contains [%k] edge-disjoint Hamilton cycles. This conjecture is similar to one due to P. Kelly [4; p. 7] that any regular tournament can be decomposed into directed Hamilton cycles, since both conjectures imply that K 2m+l is, in some sense, "strongly decomposable" into Hamilton cycles. Our conjecture would imply that any set of [i(m-l-l)] edge-disjoint Hamilton cycles of K 2m+ i could be extended to a hamiltonian decomposition of K 2m+l. Kelly's conjecture would imply that if the edges of K 2m+1 are directed in such a way that the indegrees and outdegrees of every vertex are equal, then the resulting digraph has a hamiltonian decomposition. For any graph G, let V{G) denote the set of vertices, and E(G) the set of edges, of G. For H a subgraph of G and M and N subsets of V(H) let E H {M, N) denote the set, and e w (M, N) the number of edges between the vertices of M and the vertices of N. Further, let H [M] be the subgraph …