# The Cycle-Complete Graph Ramsey Numberr(C9,K8)

Authors: M. S. A. Bataineh; M. M. M. Jaradat; L. M. N. Al-Zaleq
Journal: ISRN Algebra
 (2011)

---

## Abstract

It has been conjectured by Erdős, Faudree, Rousseau, and Schelp thatr(Cm,Kn)=(m-1)(n-1)+1 for all (m,n)≠(3,3) satisfying that m≥n≥3 (except r(C3,K3)=6). In this paper, we prove this for the case m=9 and n=8.


---

## Body

## 1. Introduction

All graphs considered in this paper are undirected and simple.Cm,Pm,Km and Sm stand for cycle, path, complete, and star graphs on m vertices, respectively. The graph K1+Pn is obtained by adding an additional vertex to the path Pn and connecting this new vertex to each vertex of Pn. The number of edges in a graph G is denoted by ℰ(G). Further, the minimum degree of a graph G is denoted by δ(G). An independent set of vertices of a graph G is a subset of the vertex setV(G) in which no two vertices are adjacent. The independence number of a graph G,α(G), is the size of the largest independent set. The neighborhood of the vertex u is the set of all vertices of G that are adjacent to u, denoted by N(u). N[u] denote to N(u)∪{u}. For vertex-disjoint subgraphs H1 and H2 of G we let E(H1,H2)={xy∈E(G):x∈V(H1),y∈V(H2)}. Let H be a subgraph of the graph G and U⊆V(G), NH(U) is defined as (⋃u∈UN(u))∩V(H). Suppose that V1⊆V(G) and V1 is nonempty, the subgraph of G whose vertex set is V1 and whose edge set is the set of those edges of G that have both ends in V1 is called the subgraph of G induced by V1, denoted by 〈V1〉G.The cycle-complete graph Ramsey numberr(Cm,Kn) is the smallest integer N such that for every graph G of order N, G contains Cm or α(G)≥n. The graph (n-1)Km-1 shows that r(Cm,Kn)≥(m-1)(n-1)+1. In one of the earliest contributions to graphical Ramsey theory, Bondy and Erdős [1] proved the following result: for all m≥n2-2,r(Cm,Kn)=(m-1)(n-1)+1. The above restriction was improved by Nikiforov [2] when he proved the equality for m≥4n+2. Erdős et al. [3] gave the following conjecture.Conjecture 1.
r(Cm,Kn)=(m-1)(n-1)+1, for all m≥n≥3 except r(C3,K3)=6.The conjecture was confirmed by Faudree and Schepl [4] and Rosta [5] for n=3 in early work on Ramsey theory. Yang et al. [6] and Bollobás et al. [7] proved the conjecture for n=4 and n=5, respectively. The conjecture was proved by Schiermeyer [8] for n=6. Jaradat and Baniabedalruhman [9, 10] proved the conjecture for n=7 and m=7,8. Later on, Chena et. al. [11] proved  the conjecture for n=7. Recently, Jaradat and Al-Zaleq [12] and Y. Zhang and K. Zhang [13], independently, proved the conjecture in the case n=m=8. In a related work, Radziszowski and Tse [14] showed that r(C4,K7)=22 and r(C4,K8)=26. In [15] Jayawardene and Rousseau proved that r(C5,K6)=21. Also, Schiermeyer [16] proved that r(C5,K7)=25. For more results regarding the Ramsey numbers, see the dynamic survey [17] by Radziszowski.Until now, the conjecture is still open. Researchers are interested in determining all the values of the Ramsey numberr(Cm,K8). In this paper our main purpose is to determine the values of r(C9,K8) which confirm the conjecture in the case m=9 and n=8. The follwoing known theorem will be used in the sequel.Theorem 1.1.
LetG be a graph of order n without a path of length k(k≥1). Then
(1.1)E(G)≤k-12n.
Further, equality holds if and only if its components are complete graphs of order k.


## 2. Main Result

In this paper we confirm the Erdős, Faudree, Rousseau, and Schelp conjecture in the caseC9 and K8. In fact, we prove that r(C9,K8)=57. It is known, by taking G=(n-1)Km-1, that r(Cm,Kn)≥(m-1)(n-1)+1. In this section we prove that this bound is exact in the case m=9 and n=8. Our proof depends on a sequence of 8 lemmas.Lemma 2.1.
LetG be a graph of order ≥57 that contains neither C9 nor an 8-elemant independent set. Then δ(G)≥8.Proof.
Suppose thatG contains a vertex of degree less than 8, say u. Then |V(G-N[u])|≥49. Since r(C9,K7)=49, as a result G-N[u] has independent set consists of 7 vertices. This set with the vertex u is an 8-elemant independent set of vertices of G. That is a contradiction.Throughout all Lemmas2.2 to 2.8, we let G be a graph with minimum degree δ(G)≥8 that contains neither C9 nor an 8-elemant independent set.Lemma 2.2.
IfG contains K8, then |V(G)|≥72.Proof.
LetU={u1,u2,u3,u4,u5,u6,u7,u8} be the vertex set of K8, Let R=G-U and Ui=N(ui)∩V(R) for each 1≤i≤8. Since δ(G)≥8,Ui≠∅ for all 1≤i≤8. Since there is a path of order 8 joining any two vertices of U, as a result Ui∩Uj=∅ for all 1≤i<j≤8 (otherwise, if w∈Ui∩Uj for some 1≤i<j≤8, then the concatenation of the uiuj-path of order 8 with uiwuj, is a cycle of order 9, a contradiction). Similarly, since there is a path of order 7 joining any two vertices of U, as a result for all 1≤i<j≤8 and for all x∈Ui and y∈Uj we have that xy∉E(G) (otherwise, if there are 1≤i<j≤8 such that x∈Ui, y∈Uj and xy∈E(G), then the concatenation of the uiuj-path of order 7 with uixyuj, is a cycle of order 9, a contradiction). Also, since there is a path of order 6 joining any two vertices of U, as a result, NR(Ui)∩NR(Uj)=∅, 1≤i<j≤8 (otherwise, if there are 1≤i<j≤8 such that w∈NR(Ui)∩NR(Uj), then the concatenation of the uiuj-path of order 6 with uixwyuj, is a cycle of order 9 where x∈Ui, y∈Uj and xw,wy∈E(G), a contradiction). Therefore |Ui∪NR(Ui)∪{ui}|≥δ(G)+1. Thus, |V(G)|≥8(δ(G)+1)≥(8)(9)=72.Lemma 2.3.
IfG contains K8-S6, then G contains K8.Proof.
LetU={u1,u2,u3,u4,u5,u6,u7,u8} be the vertex set of K8-S6 where the induced subgraph of {u1,u2,u3,u4,u5,u6,u7} is isomorphic to K7. Without loss of generality we may assume that u1u8,u2u8∈E(G). Let R=G-U and Ui=N(ui)∩V(R) for each 1≤i≤8. Then, as in Lemma 2.2, we have the following:(1)
Ui∩Uj=∅ for all 1≤i<j≤8 except possibly for i=1 and j=2.(2)
E(Ui,Uj)=∅ for all 1≤i<j≤8.(3)
NR(Ui)∩NR(Uj)=∅ for all 1≤i<j≤8.(4)
E(NR(Ui),NR(Uj))=∅ for all 1≤i<j≤8.
Sinceα(G)≤7, as a result at least five of the induced subgraphs 〈Ui∪NR(Ui)〉G, 3≤i≤8 are complete. Since δ(G)≥8, it implies that these complete graphs contain K8. Hence, G contains K8.Lemma 2.4.
IfG contains K7, then G contains K8-S6 or K8.Proof.
LetU={u1,u2,u3,u4,u5,u6,u7} be the vertex set of K7. Let R=G-U and Ui=N(ui)∩V(R) for each 1≤i≤7. Since δ(G)≥8, Ui≠∅ for all 1≤i≤7. Now we consider the following two cases.Case 1.
Ui∩Uj≠∅. for some 1≤i<j≤7, say w∈Ui∩Uj. Then it is clear that G contains K8-S6. In fact, the induced subgraph 〈U∪{w}〉G contains K8-S6.Case 2.
Ui∩Uj=∅. for all 1≤i<j≤7. Note that between any two vertices of U there are paths of order 5,6 and 7. Thus, as in Lemma 2.2, for all 1≤i<j≤7, we have the following.(1)
E(Ui,Uj)=∅.(2)
NR(Ui)∩NR(Uj)=∅.(3)
E(NR(Ui),NR(Uj))=∅.
Sinceα(G)≤7, we have that the induced subgraphs 〈Ui∪NR(Ui)〉G, 1≤i≤7 are complete. Since δ(G)≥8, it implies that these complete graphs contain K8. Hence, G contains K8.Lemma 2.5.
IfG contains K1+P7, then G contains K7.Proof.
LetU={u1,u2,u3,u4,u5,u6,u7,u8} be the vertex set of K1+P7 where K1=u1 and P7=u2u3u4u5u6u7u8. Let R=G-U and Ui=N(ui)∩V(R) for each 1≤i≤8. Now we have the following two cases.Case 1.
U4∩U6=∅. Since δ(G)≥8, Ui≠∅ for all 1≤i≤8. Now we have the following.(1)
Ui∩Uj=∅for all 2≤i<j≤8 except possibly for (i,j)∈{(3,5),(3,6),(3,7),(4,7),(5,7)} since otherwise a cycle of order 9 is produced, a contradiction.(2)
E(Ui,Uj)=∅ for all 2≤i<j≤8.(3)
NR(Ui)∩NR(Uj)=∅ for all 2≤i<j≤8.(4)
E(NR(Ui),NR(Uj))=∅ for all 2≤i<j≤8.
((2), (3), and (4) follows easily from being thatK1+P7 contains paths of order 7, 6, and 5 between any two vertices ui and uj, 2≤i<j≤8). Since α(G)≤7, as a result at least three of the induced subgraphs 〈Ui∪NR(Ui)〉G, i=2,4,5,6,8 are complete graphs. Now we have the following two assertions.
(i)  |NR(Ui)|≥7 and so |Ui∪NR(Ui)|≥8 for each i=2,8. The following is the proof of assertion (i) for i=8.
Sinceδ(G)≥8, |U8|≥1. Let y∈U8 and y is adjacent to x∈{u1,u2,u3,u4,u5,u6,u7}. Then we have the following.(i)
Ifx=u1, then u8yu1u2u3u4u5u6u7u8 is a C9, this is a contradiction.(ii)
Ifx=u2, then u8yu2u3u4u5u6u7u1u8 is a C9, this is a contradiction.(iii)
Ifx=u3, then u8yu3u2u1u4u5u6u7u8 is a C9, this is a contradiction.(iv)
Ifx=u4, then u8yu4u3u2u1u5u6u7u8 is a C9, this is a contradiction.(v)
Ifx=u5, then u8yu5u4u3u2u1u6u7u8 is a C9, this is a contradiction.(vi)
Ifx=u1, then u8yu6u5u4u3u2u1u7u8 is a C9, this is a contradiction.(vii)
Ifx=u7, then u8yu7u6u5u4u3u2u1u8 is a C9, this is a contradiction.
Sinceδ(G)≥8, |NR(y)|≥7, and so |{y}∪NR(y)|≥8. Hence, |U8∪NR(U8)|≥8. By a similar argument as above and using the symmetry of P7+K1, one can easily show that |U2∪NR(U2)|≥8.
(ii) If there is i∈{4,5,6} such that |NR(Ui)|<6, then |NR(Uj)|≥6 and so |Uj∪NR(Uj)|≥7 for any j∈{4,5,6} with i≠j. The following is the proof of assertion (ii).
Assume that|NR(U4)|<6. By (1)  U4∩Ui=∅ for all 2≤i≤8 except possibly i=4,7. Thus, for y∈U4, y is adjacent to u4 and to at most u1 and u7. Now we show that |NR(U5)|≥6. Assume |NR(U5)|<6. By (1)  U5∩Ui=∅ for all 2≤i≤8 except possibly i=3,5,7. Thus, for any w∈U5, w is adjacent to u5 and to at most u1, u3 and u7. Now, we have the following.(A)
Ifw adjacent to both u1 and u3, then u2u3wu5u6u7yu4u1u2 is a C9.(B)
Ifw adjacent to both u1 and u7, then u2u3u4yu5wu7u6u1u2 is a C9.(C)
Ifw adjacent to both u3 and u7, then u2u3wu7u6u5u4yu1u2 is a C9.
Thus,w is adjacent to at most one of u1,u3, and u7, and so |NR(U5)|≥6. We now show that |NR(U6)|≥6. As above assume |NR(U6)|<6. By (1), U6∩Ui=∅ for all 2≤i≤8 except possibly i=3,6. Thus, for w∈U6, w is adjacent to u1,u3, and u6. Hence, u8u7yu4u3wu6u5u1u8 is a C9, which implies that w is adjacent to at most one of u1 and u3 and so |NR(U6)|≥6.
Now, by using the same argument as above and taking into account thatP7+K1 is symmetry, we can easily see that if |NR(U6)|<6, then both of |NR(U4)| and |NR(U5)| are greater than or equal 6. So we need to consider the case when |NR(U5)|<6. As above, U5∩Ui=∅ for all 2≤i≤8 except possibly i=5,3 and 7. Thus, for any w∈U5, w is adjacent to u5 and to at most u1,u3 and u7. Now, assume that |NR(U4)|<6. By using (A), (B) and (C) as above and using the same arguments to get the same contradiction. Similarly, by symmetry we get that |NR(U6)|≥6.
Therefore, from(i) and (ii), at least four of the induced subgraphs 〈Ui∪NR(Ui)〉G, i=2,4,5,6,8 contain 7 vertices and so at least two of them contain K7. Thus, G contains K7.Case 2.
U4∩U6≠∅, say u9∈U4∩U6. For simplicity, in the rest of this case we consider Ui′=N(ui)∩V(R′) where R′=G-U∪{u9} and let J={2,3,5,7,8,9}. Then u2u9,u3u9,u5u9,u7u9,u8u9∉E(G) (otherwise, G contains C9) and δ(G)≥8. Hence Ui′≠∅,foralli∈J. Now we have the following assertions (see the Appendix).(1)
Ui′∩Uj′=∅ for all i,j∈J and i≠j.(2)
E(Ui′,Uj′)=∅ for all i,j∈J and i≠j.(3)
NR(Ui′)∩NR(Uj′)=∅ for all i,j∈J and i≠j.(4)
E(NR(Ui′),NR(Uj′))=∅ for all i,j∈J and i≠j.
Sinceα(G)≤7, as a result at least five of the induced subgraphs 〈Ui′∪NR(Ui′)〉G, i=2,3,5,7,8,9 are complete graphs. Since δ(G)≥8 and G contains no C9,   |NR(Ui′)|≥6 and so |Ui′∪NR(Ui′)|≥7 for each i=2,5,8,9. Therefore at least three of the induced subgraphs 〈Ui′∪NR(Ui′)〉G, i=2,3,5,7,8,9 contain K7. Thus, G contains K7.Lemma 2.6.
IfG contains K1+P6, then G contains K1+P7 or K7.Proof.
LetU={u1,u2,u3,u4,u5,u6,u7} be the vertex set of K1+P6 where K1=u1 and P6=u2u3u4u5u6u7. Let R=G-U and Ui=N(ui)∩V(R) for each 1≤i≤7. Since δ(G)≥8,|Ui|≥2 for all 1≤i≤7. Now we have the following cases.Case 1.
Ui∩Uj=∅ for all 2≤i<j≤7. Then we have the following.(1)
E(Ui,Uj)=∅ for all 2≤i<j≤7 except possibly for (i,j)∈{(3,5),(3,6),(4,6)}.(2)
NR(Ui)∩NR(Uj)=∅ for all 2≤i<j≤7.(3)
E(NR(Ui),NR(Uj))=∅ for all 2≤i<j≤7.
Sinceα(G)≤7, as a result at least one of the induced subgraphs 〈Ui∪NR(Ui)〉G, i=2,4,5,7 is complete. Since δ(G)≥8, it implies that this complete graph contains K7.Case 2.
Ui∩Uj≠∅ for some 2≤i<j≤7, say u8∈Ur∩Us. In the rest of this case we have the following subcases:Subcase 2.1.
(r,s)∈{(6,7),(5,7),(4,7),(7,3),(2,7),(5,6),(4,6),(6,3),(4,5)}. For simplicity, in the rest of this subcase we consider Ui′=N(ui)∩V(R′) where R′=G-U∪{u8} and let J={m:2≤m≤8andm∉{r,s,⌈(r+s)/s⌉+1}}. Since δ(G)≥8, then Ui′≠∅, for all  2≤i≤8. Now we have the following assertions.(1)
Ui′∩Uj′=∅ for all i,j∈J with i≠j.(2)
E(Ui′,Uj′)=∅ for all i,j∈J with i≠j.(3)
NR′(Ui′)∩NR′(Uj′)=∅ for all i,j∈J with i≠j.(4)
E(NR′(Ui′),NR′(Uj′))=∅ for all i,j∈J with i≠j.
Sinceα(G)≤7, as a result at least one of the induced subgraphs 〈Ui′∪NR′(Ui′)〉G,i∈J is complete.Since δ(G)≥8 and |Ui′|≥2 for each i∈J (because otherwise G contains K1+P7), it implies that this complete graph contains K7.Subcase 2.2.
(r,s)∉{(6,7),(5,7),(4,7),(7,3),(2,7),(5,6),(4,6),(6,3),(4,5)}. Then, by the symmetry, we have a subcase similar to Subcase 2.1.Lemma 2.7.
IfG contains K6, then G contains K1+P6 or K7.Proof.
LetU={u1,u2,u3,u4,u5,u6} be the vertex set of K6. Let R=G-U and Ui=N(ui)∩V(R) for each 1≤i≤6. Since δ(G)≥8,|Ui|≥3 for all 1≤i≤6. Now we split our work into the following two cases.Case 1.
There are1≤i<j≤6 such that Ui∩Uj≠∅, then G contains K1+P6.Case 2.
Ui∩Uj=∅ for all 1≤i<j≤6. Then we consider the following subcases.Subcase 2.1.
E(Ui,Uj)=∅ for all 1≤i<j≤6. Since between any two vertices of U there are paths of order 5 and 6, as a result NR(Ui)∩NR(Uj)=∅ and E(NR(Ui),NR(Uj))=∅ for each 1≤i<j≤6. Therefore, since α(G)≤7, at least five of the induced subgraphs 〈Ui∪NR(Ui)〉G, 1≤i≤6 are complete graphs. Since δ(G)≥8, these complete graphs contain K7. Thus, G contains K7.Subcase 2.2.
E(Ui,Uj)≠∅ for some 1≤i<j≤6, say i=1 and j=2 and u1u7u8u2 is a path. For simplicity, in the rest of this subcase we consider Ui′=N(ui)∩V(R′) where R′=G-U∪{u7,u8}. Since δ(G)≥8, then Ui′≠∅, for all  3≤i≤8. Now we have the following.(1)
Ui′∩Uj′=∅ for all 3≤i<j≤8.(2)
E(Ui′,Uj′)=∅ for all 3≤i<j≤8.(3)
NR(Ui′)∩NR(Uj′)=∅ for all 3≤i<j≤8.(4)
E(NR(Ui′),NR(Uj′))=∅ for all 3≤i<j≤8.
Therefore, sinceα(G)≤7, at least five of the induced subgraphs 〈Ui′∪NR(Ui′)〉G, 3≤i≤8 are complete graphs. Since δ(G)≥8, it implies that these complete graphs contain K7. Thus, G contains K7.Lemma 2.8.
IfG be a graph of order ≥57, then G contains K1+P6 or K6.Proof.
Suppose thatG contains neither K1+P6 nor K6. Then we have the following claims.Claim 1.
|N(u)|≤28 for any u∈V(G).Proof.
Suppose thatu is a vertex with |〈NG(u)〉G|≥29. Let 〈NG(u)〉G=⋃i=1rGi where Gi is a component for each i. 〈NG(u)〉G has minimum number of independent vertices if it has a maximum number of edges. Thus, by Theorem 1.1  Gi must be a complete graph for each i. But 〈NG(u)〉G contains no P6. Thus, Gi must be a complete graph of order at most 5. Also 〈NG(u)〉G contains no K5, thus Gi must be a complete graph of order at most 4. Hence, the minimum number of independent vertices of 〈NG(u)〉 occurs only if 〈NG(u)〉 contains either a 7 tetrahedrons and an isolated vertex or 6 tetrahedron, a triangle and a K2 or 6 tetrahedrons and 2 triangles. In any of these cases α(G)≥8. This is a contradiction. The proof of the claim is complete.Claim 2.
α(G)=7.Proof.
Since|V(G)|≥57 and G contains no C9 and since r(C9,K7)=49,α(G)≥7. But G has no 8-element independent set, so α(G)≤7. Thus, α(G)=7. The proof of the claim is complete.
Now, for any 7 independent verticesu1,u2,u3,u4,u5,u6, and u7, set Ni[ui+1]=N[ui+1]-(⋃j=1iN[uj]),1≤i≤6. Analogously, we set Ni(ui+1),   1≤i≤6. Let A=⋃i=16Ni[ui+1],    B=⋃i=16Ni(ui+1), and β=α(〈B〉G).
Claim 3.
|N(u1)∪B|≥50.Proof.
Suppose that|N(u1)∪B|≤49. Then |N[u1]∪A|≤56. And so |G-(N[u1]∪A)|≥57-56=1. But r(C9,K1)=1, so G-(N[u1]∪A) contains a vertex, say u8, which is not adjacent to any of u1,u2,u3,u4,u5,u6, and u7. Thus, {u1,u2,u3,u4,u5,u6,u7,u8} is an 8-element independent set. Therefore, α(G)≥8. That is a contradiction. The proof of the claim is complete.Now, by Lemma2.1, δ(G)≥8 and so by Claim 1, we have that 8≤|N(u1)|≤28. Thus, if |N(u1)|=r,then |B|≥50-r. By a similar argument as in Claim 1, we have that α(〈N(u1)〉G)≥⌈r/4⌉ and β≥⌈(50-r)/4⌉. Note that for any 8≤r≤21,⌈(50-r)/4⌉ is greater than or equal to 8. And so α(G)≥8. Now we have the following cases.Case 1.
22≤|N(u1)|≤25, then by a similar argument as in Claim 1, we have that α(〈N(u1)〉G)≥6 and β≥7. Then, 〈B〉G has an independent set which consists of 7 vertices. This set with the vertex u1 is an 8-element independent set of vertices of G. That is a contradiction.Case 2.
|N(u1)|=26, then |B|≥24. By a similar argument as in Claim 1, we have that α(〈N(u1)〉G)≥7 and β≥6. Now we have the following two subcases.Subcase 2.1.
β≥7. Then we have a subcase similar to Case 1.Subcase 2.2.
β=6. The best case of such subgraph is the graph that shown in Figure 1. Now we have the following two subcases.
Subcase 2.2.1. There is a vertex of ⋃i=16Ni(ui+1), say a1, that is not adjacent to at least one vertex of each K(j)(1≤j≤7), say xj. Then {x1,x2,x3,x4,x5,x6,x7,a1} is an 8-elemant independent set of vertices of G. And so α(G)≥8. That is a contradiction.
Subcase 2.2.2. For each vertex of ⋃i=16Ni(ui+1) there is 1≤j≤7  such that this vertex is adjacent to all vertices of K(j). Then G contains K1+P6 or C9. That is a contradiction.Figure 1
Describes the situation in Subcase2.2.Case 3.
27≤|N(u1)|≤28, Then by using the same argument as in Case 2, we have the same contradiction.Theorem 2.9.
r(C9,K8)=57. 						Proof.
Suppose that there exists a graphG of order 57 that contains neither C9 nor an 8-elements independent set. Then by Lemma 2.1,  δ(G)≥8 and by Lemma 2.8, G contains K1+P6 or K6. Thus, by Lemmas 2.7, 2.6, 2.5, 2.4, 2.3, and 2.2, we have that |V(G)|≥72. That is a contradiction. The proof is complete.



---

*Source: 926191-2011-07-21.xml*