Yanbo Zhanga,b, Hajo Broersma^b , Yaojun Chen^a

^aDepartment of Mathematics, Nanjing University, Nanjing 210093, P.R. China ^bFaculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands

ybzhang@163.com, h.j.broersma@utwente.nl, yaojunc@nju.edu.cn

Given two graphs G¹ and G2, the Ramsey number R(G1, G2) is the smallest integer N such that, for any graph G of order N, either G¹ is a subgraph of G, or G² is a subgraph of the complement of G. Let Cⁿ denote a cycle of order n, Wⁿ a wheel of order n + 1 and Sⁿ a star of order n. In this paper, it is shown that R(Wn, C4) = R(Sn+1, C4) for n ≥ 6. Based on this result and Parsons' results on R(Sn+1, C4), we establish the best possible general upper bound for R(Wn, C4) and determine some exact values for R(Wn, C4).

Keywords: Ramsey number; star; wheel; quadrilateral Mathematics Subject Classification : 05C55, 05D10

1. Introduction

In this note we deal with finite simple graphs only. For a nonempty proper subset S ⊆ V (G), let G[S] and G − S denote the subgraph induced by S and V (G) − S, respectively. Let NS(v) be the set of all the neighbors of a vertex v that are contained in S, let NS[v] = NS(v) ∪ {v} and let dS(v) = |NS(v)|. If S = V (G), we write N(v) = NG(v), N[v] = N(v) ∪ {v} and d(v) = dG(v). For two vertex-disjoint graphs G¹ and G2, G¹ + G² is the graph obtained from G¹ ∪ G² by joining every vertex of G¹ to every vertex of G2. A star, a cycle and a complete graph of order n are denoted by Sn, Cⁿ and Kn, respectively. A wheel Wⁿ = K¹ +Cⁿ is a graph of order n+ 1. We use

Received: 01 May 2014, Revised: 01 September 2014, Accepted: 07 September 2014.

∆(G), δ(G) and α(G) to denote the maximum degree, the minimum degree and the independence number, respectively, of a graph G.

Given two graphs G¹ and G2, the Ramsey number R(G1, G2) is the smallest integer N such that, for any graph G of order N, either G contains G¹ or G contains G2, where G is the complement of G. It is well-known that it is difficult to deal with some extremal problems involving C4. In this note, we are interested in the relationship between two Ramsey numbers involving C4, that is, R(Sn+1, C4) and R(Wn, C4). The former has been well-studied and the latter has received more attention recently.

Parsons [6] began to consider the Ramsey numbers R(Sn+1, C4) back in 1975. By using the existence of projective planes over Galois fields and the generalized friendship theorem, in [6] he established upper bounds for R(Sn+1, C4) and determined the exact values for several specific values of n, as expressed in the following two results.

Theorem 1.1. (Parsons [6]). R(Sn+1, C4) ≤ n + b √ n − 1c + 2 for all n ≥ 2, and if n = q ² + 1 and q ≥ 1, then R(Sn+1, C4) ≤ n + b √ n − 1c + 1.

Theorem 1.2. (Parsons [6]). If q is a prime power, then R(S^{q 2}+1, C4) = q ²+q+1 and R(S^{q 2}+2, C4) = q ² + q + 2.

Noting that if n = q 2 , then n + b √ n − 1c + 2 = q ² + q + 1, we see that the general bound for R(Sn+1, C4) in Theorem 1.1 is best possible.

Obviously, Sn+1 is a (spanning) subgraph of Wⁿ and so R(Wn, C4) ≥ R(Sn+1, C4). By using an exhaustive computer search, Tse [10] was able to calculate the value of R(Wn, C4) for 3 ≤ n ≤ 12. An interesting question in this respect is: what is the best possible upper bound for R(Wn, C4)? Surahmat et al. [9] showed that R(Wn, C4) ≤ n + dn/3e + 1 for n ≥ 6. Clearly, this upper bound is not tight in general. Because R(Wn, C4) ≥ R(Sn+1, C4) showing that the best bound for R(Wn, C4) is at least n + b √ n − 1c + 2, one may ask whether R(Wn, C4) − R(Sn+1, C4) is a constant or a function depending on n. Recently, by using Reiman's theorem [8] on the Turan number ´ t(n, C4), Ore's theorem [5] on Hamiltonicity, a result of Faudree and Schelp [3] on R(Cn, C4) and the Erdos-R ˝ enyi graph, Dybizba ´ nski and Dzido [2] established a general ´ upper bound for R(Wn, C4) for n ≥ 10 and determined some exact values of R(Wn, C4). We summarized some of their results in the following theorem.

Theorem 1.3. (Dybizbanski and Dzido [2]). ´ R(Wn, C4) ≤ n + b √ n − 1c + 2 for all n ≥ 10, and if q ≥ 4 is a prime power, then R(W^{q 2} , C4) = q ² + q + 1.

In the same paper, with the help of computers, they determined the exact values of some Ramsey numbers for a small wheel versus a C4.

Theorem 1.4. (Dybizbanski and Dzido [2]). ´ R(Wn, C4) = n + 5 for 13 ≤ n ≤ 16.

Clearly, Theorem 1.3 implies that Parsons' bound for R(Sn+1, C4) is also a best possible upper bound for R(Wn, C4) if n ≥ 10. In an unpublished paper, Wu et al. [11] obtained nine new values for R(Wn, C4); as in the other cases their calculations have been performed with the aid of computer search.

Theorem 1.5. (Wu et al. [11]) R(Wn, C4) = n + 5 for 17 ≤ n ≤ 20; R(W26, C4) = 32; R(Wn, C4) = n + 7 for 34 ≤ n ≤ 36; R(W43, C4) = 51.

The exact values of the Ramsey numbers R(Sn+1, C4) for n ≤ 6 can be found in [7]. For the value of R(S8, C4), we get R(S8, C4) ≤ 11 by Theorem 1.1. Since the Petersen graph contains no C⁴ and its complement has no S8, we get R(S8, C4) ≥ 11 and so we obtain that R(S8, C4) = 11. Using Theorem 1.2, we can get the exact values of R(Sn+1, C4) for n = 9, 10, 16, 17. By considering Theorems 1.1, 1.2 and 1.3, and these known values of R(Sn, C4) and R(Wn, C4) for small n ≥ 6, we observe that there is an infinite number of values of n for which R(Wn, C4) = R(Sn+1, C4). Motivated by this observation, a natural question is whether this equality holds in general. In this note, we give an affirmative answer to this question. Our main result is as follows.

Theorem 1.6. \[R(W_n, C_4) = R(S_{n+1}, C_4)\] for \(n \ge 6\).

We postpone our proof of this result to the next section.

By Theorem 1.6, we see that the two functions R(Wn, C4) and R(Sn+1, C4) are in fact the same when n ≥ 6. Because the Ramsey numbers R(Sn+1, C4) are well-studied, we can use Theorem 1.6 and known results on R(Sn+1, C4) to establish new results on R(Wn, C4). Of course, we can do that in reverse as well. Up to now, most known values of R(Wn, C4) for small n are obtained with the help of computers. Because finding an Sn+1 is much easier than finding a Wⁿ in a graph using computers, we can focus our calculation on R(Sn+1, C4) by computers instead of R(Wn, C4) if we want to determine some values of R(Wn, C4) with the help of computers.

Combining Theorems 1.1, 1.2 and 1.6, we obtain the following.

Theorem 1.7. R(Wn, C4) ≤ n + b √ n − 1c + 2 for n ≥ 6, and if n = q ² + 1 and q ≥ 3, then R(Wn, C4) ≤ n + b √ n − 1c + 1. Furthermore, if q ≥ 3 is a prime power, then we have R(W^{q 2} , C4) = q ² + q + 1 and R(W^{q 2}+1, C4) = q ² + q + 2.

Clearly, Theorem 1.7 is stronger than Theorem 1.3. Furthermore, by Theorems 1.1-1.7 and some other known results on R(Sn+1, C4), we can summarize several exact values (see Table 1) for R(Wn, C4) and R(Sn+1, C4) when n ≥ 6 is small. Here the numbers marked with ∗ are obtained from the results in this paper, and the numbers marked with ? can be obtained by Theorem 1.7 avoiding computer search.

Table 1: Exact values of R(Wn, C4) and R(Sn+1, C4) for 6 ≤ n ≤ 43.

As for the lower bounds of R(Sn+1, C4), Burr et al. [1] showed that R(Sn+1, C4) > n + √ n − 6n ¹¹/⁴⁰. In the same paper, they proposed the following conjecture, for which Erdos, one of the ˝ authors, offered $100 for a proof or disproof.

Conjecture 1. (Burr et al. [1]). R(Sn+1, C4) < n + √ n − c holds infinitely often, where c is an arbitrary constant.

After an easy calculation, we find that all exact values of R(Sn+1, C4) listed in Table 1 satisfy R(Sn+1, C4) ≥ n + d √ ne. Thus we finish this section by posing the following intriguing problem.

Question. Is it true that \[R(W_n, C_4) = R(S_{n+1}, C_4) \ge n + \lceil \sqrt{n} \rceil\] for all \(n \ge 6\)?

2. Proof of Theorem 1.6

In order to prove Theorem 1.6, we need the following four lemmas.

Lemma 2.1. (Faudree and Schelp [3]). R(Cn, C4) = n + 1 for n ≥ 6.

Lemma 2.2. (Tse [10]). R(W6, C4) = 9, R(Wn, C4) = n + 4 for 7 ≤ n ≤ 10.

Lemma 2.3. (Faudree et al. [4]). R(S7, C4) = 9.

Lemma 2.4. (Zhang et al. [12]) Let C be a longest cycle in a graph G and u ∈ V (G) − V (C). Then α(G) ≥ dC(u) + 1.

Proof of Theorem 1.6. We first prove that R(Sn+1, C4) ≥ n+4 for n ≥ 7. Let k = b(n+1)/4c and C = x1x2...x4kx¹ be a cycle of length 4k. Set X¹ = {x1, x2}, X² = {x3, x4}, X³ = {xⁱ | i ≡ 1, 2 (mod 4) and i ≥ 5} and X⁴ = {xⁱ | i ≡ 0, 3 (mod 4) and i ≥ 5}. We now construct a graph F of order n + 3 from C as follows: V (F) = V (C) ∪ {zⁱ | 1 ≤ i ≤ l}, where 4k + l = n + 3. If n ≡ 3 (mod 4), then let N(z1) = X¹ ∪ X³ and N(z2) = X² ∪ X4; if n ≡ 0 (mod 4), then let N(z1) = X¹ ∪ {z2}, N(z2) = X³ ∪ {z1} and N(z3) = X² ∪ X4; if n ≡ 1 (mod 4), then let N(z1) = X¹ ∪ {z2}, N(z2) = X³ ∪ {z1}, N(z3) = X² ∪ {z4} and N(z4) = X⁴ ∪ {z2}; if n ≡ 2 (mod 4), then let N(z1) = X¹ ∪ {z2}, N(z2) = X³ ∪ {z1}, N(z3) = X² ∪ {z4}, N(z4) = X⁴ ∪ {z2} and N(z5) = {z1, z2, z3, z4}. It is easy to check that F has no C⁴ and δ(F) ≥ 3. Therefore, R(Sn+1, C4) ≥ n + 4 for n ≥ 7.

Since Sn+1 ⊆ Wn, we have R(Wn, C4) ≥ R(Sn+1, C4). By Lemmas 2.2 and 2.3, we see that R(W6, C4) = R(S7, C4) and R(Wn, C4) = n + 4 for 7 ≤ n ≤ 10. Since R(Sn+1, C4) ≥ n + 4 for n ≥ 7, we get that R(Wn, C4) = R(Sn+1, C4) for 7 ≤ n ≤ 10. Now it remains to show that R(Wn, C4) ≤ R(Sn+1, C4) for n ≥ 11. Let G be a graph of order N = R(Sn+1, C4) ≥ n + 4. Set v ∈ V (G) with d(v) = ∆(G), Z = V (G) − N[v]. Suppose to the contrary that neither G contains a Wⁿ nor G contains a C4. Thus, noting that N = R(Sn+1, C4), we have d(v) ≥ n. If d(v) ≥ n+1, then by Lemma 2.1, G[N(v)] contains a Cn, which together with v forms a Wⁿ in G, a contradiction. Hence we have ^d(v) = ⁿ. By Theorem 1.1, ^|Z^{| = N −} (ⁿ + 1) ≤ b√ n − 1c + 1. Let C be a longest cycle in G[N(v)]. By Lemma 2.1, we have |C| ≥ n − 1, and so |C| = n − 1. Set u = N(v) − V (C). If dC(u) ≥ 3, then by Lemma 2.4, α(G[N(v)]) ≥ 4, which implies that G contains a C4, and hence dC(u) ≤ 2. If there exists some vertex y ∈ V (G) − {u} such that y has two nonadjacent vertices y1, y² ∈ V (C) − NC(u), then uy1yy2u is a C⁴ in G, and hence y has at most one nonadjacent vertex in V (C) − NC(u) for each y ∈ V (G) − {u}. Since n ≥ 11, ^|Z| ≤ b√ n − 1c + 1 and dC(u) ≤ 2, we have

\[|V(C) - N_C(u)| - |N_C(u) \cup Z| = |C| - d_C(u) - |Z| - d_C(u) \ge (n-1) - 2 - (\lfloor \sqrt{n-1} \rfloor + 1) - 2 \ge 2.\]

Because every vertex of NC(u) ∪ Z has at least |V (C) − NC(u)| − 1 adjacent vertices in V (C) − NC(u), by the Pigeonhole Principle, there exists some vertex w ∈ V (C) − NC(u) such that NC(u) ∪ Z ⊆ N(w). Noting that w has at most one nonadjacent vertex in V (C) − NC(u) and wv ∈ E(G), we have

d(w) ≥ |V (C) − NC(u)| − 2 + |NC(u) ∪ Z| + 1 = |C| + |Z| − 1 = N − 3 ≥ n + 1, which contradicts the fact that d(v) = ∆(G) = n.

This completes the proof of Theorem 1.6.

Acknowledgement

This research was supported by NSFC under grant numbers 11071115, 11371193 and 11101207.

References

• [1] S.A. Burr, P. Erdos, R.J. Faudree, C.C. Rousseau and R.H. Schelp, Some complete bipartite ˝ graph-tree Ramsey numbers, Annals of Discrete Mathematics 41 (1989), 79–89.
• [2] J. Dybizbanski and T. Dzido, On some Ramsey numbers for quadrilaterals versus wheels, ´ Graphs and Combinatorics 30 (2014), 573–579.
• [3] R.J. Faudree and R.H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Mathematics 8 (1974), 313–329.
• [4] R.J. Faudree, C.C. Rousseau and R.H. Schelp, Small order graph-tree Ramsey numbers, Discrete Mathematics 72 (1988), 119–127.
• [5] O. Ore, Note on Hamilton circuits, American Mathematical Monthly 67 (1960), 55.
• [6] T.D. Parsons, Ramsey graphs and block designs I, Transactions of the American Mathematical Society 209 (1975), 33–44.
• [7] S.P. Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics (2011), DS1.13.
• [8] I. Reiman, Uber ein Problem von K. Zarankiewicz, Acta Mathematica Academiae Scientiarum Hungarica 9 (1958), 269–279.
• [9] Surahmat, E.T. Baskoro, S. Uttunggadewa and H.J. Broersma, An upper bound for the Ramsey number of a cycle of length four versus wheels, LNCS 3330, Springer, Berlin (2005), 181–184.
• [10] K.K. Tse, On the Ramsey number of the quadrilateral versus the book and the wheel, Australasian Journal of Combinatorics 27 (2003), 163–167.
• [11] Y.L. Wu, Y.Q. Sun and S. Radziszowski, Wheel and star-critical Ramsey numbers for quadrilateral, http://www.cs.rit.edu/∼spr/PUBL/wsr13.pdf
• [12] L.M. Zhang, Y.J. Chen and T.C. Edwin Cheng, The Ramsey numbers for cycles versus wheels of even order, European Journal of Combinatorics 31 (2010), 254–259.