-
A Rainbow Version of Ore Theorem
- GAO Liqing, WANG Jian
-
2023, 32(10):
108-113.
DOI: 10.12005/orms.2023.0327
-
Asbtract
(
)
PDF (1009KB)
(
)
-
References |
Related Articles |
Metrics
Let G1,G2,···,Gn 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 {G1,G2,···,Gn}. Similarly, if P is a path of length n-1 such that each edge belongs to a different graph of G1,G2,···,Gn-1, then we call P a rainbow Hamilt on path on {G1,G2,···,Gn-1}. Recently, Joos and Kim have proved a rainbow version of Dirac theorem, i.e., if each of G1,G2,···,Gn has minimum degree at least n/2, then {G1,G2,···,Gn} contains a rainbow Hamilton cycle. In this paper, by the shifting method we show that if each of G1,G2,···,Gn has at least $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+2$ edges, then {G1,G2,···,Gn} contains a rainbow Hamilton cycle. Moreover, if each of G1,G2,···,Gn-1 has at least $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+1$ edges, then {G1,G2,···,Gn-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 {G1,G2,···,Gn} does not contain a rainbow Hamilton cycle, then one can apply the shifting operator to G1,G2,···,Gn simultaneously without producing a rainbow Hamilton cycle. By applying the shifting operator to G1,G2,···,Gn repeatedly, eventually we shall obtain a sequence of shifted graphs G1,G2,···,Gn.
For two pairs (x1,x2)and (y1,y2), define the shifted partial order＜as: (x1,x2)＜(y1,y2) if and only if either x1≤y1 and x2≤y2 or x1≤y2 and x2≤y1 hold. The shifted graphs have the following nice property: if x1x2 is an edge of G and G is shifted, then for any pair (x1,x2)＜(y1,y2),y1y2 is also an edge of G. Let Hn,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 Hn,a,b is a shifted graph. Moreover, Hn,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 Gi has to be a subgraph of Hn,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 f1={1,2k},f2={2,2k-1},···,fk={k,k+1}and let fk+1={2,2k},fk+2={3,2k-1},···,f2k-1={k,k+2},f2k={1,k+1}. Then f1,f2,···,f2k form a Hamilton cycle. Since {G1,G2,···,Gn} does not contain a rainbow Hamilton cycle, we infer that there exists i such that fi$\notin$Gi. If i=2k, then {1,k+1}$\notin$E(Gn). By using the property of shifted graphs, we obtain that Gi has to be a subgraph of H2k,k,0. If i≤k, then we have fi={i,2k+1-i}$\notin$E(Gi). It follows that Gi has to be a subgraph of H2k,2k-i,i-1. If i≥k, set j=i-k, then fi={j,2k-j}$\notin$E(Gi). Since fi＜fj={j,2k+1-j},fj$\notin$E(Gi). Then we can show that Gi has to be a subgraph of H2k,2k-j,j-1.
For n=2k+1, let f1={1,2k+1},f2={2,2k},···,fk={k,k+2}and let fk+1={2,2k+1},fk+2= {3,2k},···,f2k={k+1,k+2},f2k+1={1,k+1}. It is easy to see that these edges form a Hamilton cycle. Since {G1,G2,···,Gn}does not contain a rainbow Hamilton cycle, there exists i such that fi$\notin$Gi. If i=2k+1,then {1,k+1}$\notin$E(Gi). Then Gi has to be a subgraph of H2k+1,k,0. If i≥k+1, set j=i-k, then fi={j+1,2k+2-j}$\notin$E(Gi), implying that Gi has to be a subgraph of H2k+1,2k+1-j,j. If 1≤i≤k, then fi={i,2k+2-i}$\notin$E(Gi). As f′={i+1,2k+2-i} satisfies fi＜f′,Gi has to be a subgraph of H2k+1,2k+1-i,i. By computations, we show that all these Hn,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 G1,G2,···,Gn has at least $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+2$ edges, then{G1,G2,···,Gn} contains a rainbow Hamiltonian cycle. By a similar argument, we establish the corresponding result for rainbow Hamiltonian paths as well.
