The Cycle-complete Graph Ramsey Number R(C₁₁,K₈)

The Ramsey theory is the focus of research in the graph theory. It is the origin of the random graph theory. It is a wide range of the study about the cycle-complete graph Ramsey number. The cycle-complete graph Ramsey number r(Cm, Kn) is the smallest integer N such that for any graph G of order N, G contains Cm or a(G)≥n. In1978, Erdos et al. posed the following conjecture:r(Cm,Kn)=(m-1)(n-1)+1for all m≥n≥3, except r(C3,K3)=6.A cycle of order n is denoted by Cn. A subset S of V is called an independent set of G if no two vertices of S are adjacent in G. The number of vertices in a maximum independent set of G is called the independence number of G and is denoted by α(G). A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph. A complete graph on n vertices is denoted by Kn. A wheel of order n+1is Wn=K1+Cn and Wn-is a graph. which is obtained from Wn by deleting a spoke from Wn.According to the contents, this paper is divided into three chapters.In chapter1, we introduce some definitions, and introduce the development of the cycle-complete graph Ramsey number. We also introduce a famous conjecture.In chapter2, in order to prove the conjecture by contradiction, suppose that there exists a extremal graph which contradicts with the conjecture, i.e., let G be a graph of order71which contains neither C11nor an8-element independent set. We study the extremal graph and obtain the following10Lemmas:Lemma1.δ(G)≥10. Lemma2. G contains no W9.Lemma3. G contains no K1+P9. Lemma4. G contains no W9-.Lemma5. G contains no W8. Lemma6. G contains no K8.Lemma7. G contains no K1+P8. Lemma8. G contains no W8-.Lemma9. G contains no K7. Lemma10. G contains no K1+P7.Applying these10Lemmas, we have obtained the Main theorem:Theorem11. r(C11,Ks)=71.Hence the conjecture holds.In chapter3, we give the appendix of this paper.