关键词: Ore定理, 彩色哈密尔顿圈, 彩色哈密尔顿路

Abstract: Let G₁,G₂,···,G_n be n graphs on the same vertex set V with |V|=n. If C is a cycle of length n such that each edge belongs to a different graph, then we call C a rainbow Hamilton cycle on {G₁,G₂,···,G_n}. Similarly, if P is a path of length n-1 such that each edge belongs to a different graph of G₁,G₂,···,G_n-1, then we call P a rainbow Hamilt on path on {G₁,G₂,···,G_n-1}. Recently, Joos and Kim have proved a rainbow version of Dirac theorem, i.e., if each of G₁,G₂,···,G_n has minimum degree at least n/2, then {G₁,G₂,···,G_n} contains a rainbow Hamilton cycle. In this paper, by the shifting method we show that if each of G₁,G₂,···,G_n has at least $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+2$ edges, then {G₁,G₂,···,G_n} contains a rainbow Hamilton cycle. Moreover, if each of G₁,G₂,···,G_n-1 has at least $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+1$ edges, then {G₁,G₂,···,G_n-1} contains a rainbow Hamilton path.
The shifting operator is a powerful tool in extremal set theory, which was invented by Erdös, Ko and Rado and further developed by Frankl. The shifting operator can be applied to graphs and hypergraphs and preserve the number of edges. It is well known that the shifting operator cannot increase the matching number of graphs and hypergraphs. In the present paper, we show that if a graph system {G₁,G₂,···,G_n} does not contain a rainbow Hamilton cycle, then one can apply the shifting operator to G₁,G₂,···,G_n simultaneously without producing a rainbow Hamilton cycle. By applying the shifting operator to G₁,G₂,···,G_n repeatedly, eventually we shall obtain a sequence of shifted graphs G₁,G₂,···,G_n.
For two pairs (x₁,x₂)and (y₁,y₂), define the shifted partial order＜as: (x₁,x₂)＜(y₁,y₂) if and only if either x₁≤y₁ and x₂≤y₂ or x₁≤y₂ and x₂≤y₁ hold. The shifted graphs have the following nice property: if x₁x₂ is an edge of G and G is shifted, then for any pair (x₁,x₂)＜(y₁,y₂),y₁y₂ is also an edge of G. Let H_n,a,b be a graph with the vertex set {1,2,···,n} such that (i)the subgraph induced by {1,2,···,a} is a complete graph; (ii){a+1,a+2,···,n} forms an independent set; (iii)The neighbors of x are 1,2,···,b for each x in{a+1,a+2,···,n}. It is easy to see that H_n,a,b is a shifted graph. Moreover, H_n,a,b is non-Hamiltonian if n-a≥b and a≥b.
By applying a technique developed by Akiyama and Frankl, we show that some G_i has to be a subgraph of H_n,a,b for some a and b. We prove the result by distinguishing two cases: n is odd and n is even. For n=2k, let f₁={1,2k},f₂={2,2k-1},···,f_k={k,k+1}and let f_k+1={2,2k},f_k+2={3,2k-1},···,f_2k-1={k,k+2},f_2k={1,k+1}. Then f₁,f₂,···,f_2k form a Hamilton cycle. Since {G₁,G₂,···,G_n} does not contain a rainbow Hamilton cycle, we infer that there exists i such that f_i$\notin$G_i. If i=2k, then {1,k+1}$\notin$E(G_n). By using the property of shifted graphs, we obtain that G_i has to be a subgraph of H_2k,k,0. If i≤k, then we have f_i={i,2k+1-i}$\notin$E(G_i). It follows that G_i has to be a subgraph of H_2k,2k-i,i-1. If i≥k, set j=i-k, then f_i={j,2k-j}$\notin$E(G_i). Since f_i＜f_j={j,2k+1-j},f_j$\notin$E(G_i). Then we can show that G_i has to be a subgraph of H_2k,2k-j,j-1.
For n=2k+1, let f₁={1,2k+1},f₂={2,2k},···,f_k={k,k+2}and let f_k+1={2,2k+1},f_k+2= {3,2k},···,f_2k={k+1,k+2},f_2k+1={1,k+1}. It is easy to see that these edges form a Hamilton cycle. Since {G₁,G₂,···,G_n}does not contain a rainbow Hamilton cycle, there exists i such that f_i$\notin$G_i. If i=2k+1,then {1,k+1}$\notin$E(G_i). Then G_i has to be a subgraph of H_2k+1,k,0. If i≥k+1, set j=i-k, then f_i={j+1,2k+2-j}$\notin$E(G_i), implying that G_i has to be a subgraph of H_{2k+1,2k+1-j,j}. If 1≤i≤k, then f_i={i,2k+2-i}$\notin$E(G_i). As f′={i+1,2k+2-i} satisfies f_i＜f′,G_i has to be a subgraph of H_{2k+1,2k+1-i,i}. By computations, we show that all these H_n,a,b graphs have at most $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+1$ edges, which leads to a contradiction. Thus, we conclude that if each of G₁,G₂,···,G_n has at least $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+2$ edges, then{G₁,G₂,···,G_n} contains a rainbow Hamiltonian cycle. By a similar argument, we establish the corresponding result for rainbow Hamiltonian paths as well.

Key words: Ore theorem, rainbow Hamiltonian cycle, rainbow Hamiltonian path