A note on the Ramsey number for a cycle with respect to a disjoint union of wheels

I Wayan Sudarsana

Algebra and Combinatorics Research Group (ACRG), Department of Mathematics, Faculty of Mathematics and Natural Sciences, Tadulako University, Jalan Soekarno-Hatta Km. 9 No. 1 Palu 94118, Indonesia

sudarsanaiw1972@gmail.com

Let Kⁿ be a complete graph with n vertices. For graphs G and H, the Ramsey number R(G, H) is the smallest positive integer n such that in every red-blue coloring on the edges of Kn, there is a red copy of graph G or a blue copy of graph H in Kn. Determining the Ramsey number R(Cn, tWm) for any integers t ≥ 1, n ≥ 3 and m ≥ 4 in general is a challenging problem, but we conjecture that for any integers t ≥ 1 and m ≥ 4, there exists n⁰ = f(t, m) such that cycle Cⁿ is tWm–good for any n ≥ n0. In this paper, we provide some evidence for the conjecture in the case of m = 4 that if n ≥ n⁰ then the Ramsey number R(Cn, tW4) = 2n + t − 2 with n⁰ = 15t ² − 4t + 2 and t ≥ 1. Furthermore, if G is a disjoint union of cycles then the Ramsey number R(G, tW4) is also derived.

Keywords: Ramsey number, cycle, wheel Mathematics Subject Classification : 05C55

DOI: 10.5614/ejgta.2021.9.2.24

1. Introduction

A notation G(V, E), in short denoted as G, is a graph with the vertex set V and the edge set E. In this paper, we mention that all graphs are simple, undirected and finite. For subgraph H of G, a subgraph G − H of G is constructed from G by deleting the vertex set and the edge set of H including all edges incident to the vertex set of H. Let A be any subset of the vertex set V of G,

Received: 15 July 2020, Revised: 31 May 2021, Accepted: 15 August 2021.

then the induced subgraph G[A] of G, is the graph with the vertex set A and the edge set consists of all of the edges in E having both endpoints in A. We follow that the complement of a graph G is a graph \(\overline{G}\) having the same vertex set V such that two any distinct vertices u, v in V of \(\overline{G}\) are adjacent if and only if u and v are not adjacent in G. On the disjoint union of graphs, we use the definition as follow: for positive integers t and t with t and t and t and t are respectively the vertex set and the edge set of connected graph \(G_t\). The disjoint union of graphs, \(\bigcup_{i=1}^t G_i\), is a graph with the vertex set \(\bigcup_{i=1}^t V_i\) and the edge set \(\bigcup_{i=1}^t E_i\); and if \(G_t \simeq G\) for each t then \(\bigcup_{i=1}^t G_i = tG\).

For the definition of Ramsey number, we cite the results proposed by Sudarsana [13], [11], [12]; that is, for graphs G and H, the Ramsey number R(G,H) is the smallest natural number n such that in every red and blue colorings of the edges of the complete graph \(K_n\), there is a graph G in \(K_n\) which is all edges are red or a graph H in \(K_n\) which is all edges are blue. In the other terminology, a graph F is called (G,H)-free, if F contains no G and \(\overline{F}\) contains no H. Furthermore, we have an equivalent definition of Ramsey number R(G,H), that is, the smallest positive integer n such that there is no (G,H)-free graph on n vertices exists.

For graphs G and H with |G|=n, the chromatic number of H is \(\chi\) and \(\sigma\) is the chromatic surplus of H, that is, the minimum cardinality of a color class taken over all proper colorings of H with \(\chi\) colors. By using this basic terminology, in 1981 Burr [4] have been proposed the general lower bound of the Ramsey number R(G,H), that is

\[R(G,H) \ge (n-1)(\chi - 1) + \sigma \tag{1}\]

and the graph G is called H-good when the inequality in equation (1) is equals. The colletion known values of classical Ramsey number r(n,m) and Ramsey number of graph R(G,H) can be found in the dynamic survey of Radziszowski [8], in the other hand its applications colleted by Rosta [9]. On this paper, we denote by \(W_m\) for a wheel on m+1 vertices. The notation \(tW_m\) discribe a graph with t copies of wheels of order m+1. Surahmat et al. [14] proved that cycle \(C_n\) is \(W_m\)-good; Chen et al. [6] showed that \(P_n\) is \(W_m\)-good for even m and \(n \ge m-1 \ge 3\); \(P_n\) is \(tW_4\)-good for \(n \ge 15t^2 - 4t + 2\), \(t \ge 1\) [13], and Sudarsana [12] recently proved that \(C_n\) is \(tK_m\)-good. Meanwhile, \(S_n\) is not \(W_6\)-good for \(n \ge 3\) [5].

In the case of \(H \simeq tW_m\), the chromatic surplus \(\sigma(H)\) equals t. In general, determining Ramsey number \(R(C_n, tW_m)\) for any \(m \geq 4\) is a notoriously hard problem. The following theorem shows that if \(n \geq n_0\) then the cycle \(C_n\) is \(tW_4\)-good with \(n_0 = 15t^2 - 4t + 2\) and \(t \geq 1\).

Theorem 1.1. For \[t \ge 1\] and \(f(t) = 15t^2 - 4t + 2\). If \(n \ge f(t)\) then \(R(C_n, tW_4) = 2n + t - 2\).

In proving of Theorem 1.1, we use the result of Bondy [3] stated below and the above mentioned result of Surahmat et al. [14].

Lemma 1.1. [3] Let G be a graph of order n. If the minimum degree of G satisfies \(\delta(G) \geq \frac{n}{2}\) then either G is pancyclic or n is even and \(G \simeq K_{\frac{n}{2},\frac{n}{2}}\).

Theorem 1.2. [14] Let n and m be positive integers. If m is even and \(n \geq \frac{5m}{2} - 1\) then \(R(C_n, W_m) = 2n - 1\).

Let G be a graph containing all H-good components, the general formula for finding the exact value of Ramsey number R(G, H) have been found by Bielak [2] and Sudarsana et al. [11]. In some particular graphs, showed by Stahl [10] and Baskoro et al. [1]. Hence, these results give a motivation to study the families of graphs which have H-good properties.

In particular, when G is a disjoint union of cycles then by using the results of Sudarsana et al. [11] and Theorem 1.1 we obtain the Corollary 1.1 below for finding the exact value of Ramsey number \(R(G, tW_4)\).

Corollary 1.1. Let t and k be positive integers and \(f(t) = 15t^2 - 4t + 2\). Let \(G \simeq \bigcup_{i=1}^k l_i C_{n_i}\), where \(l_i \geq 1\) and each \(C_{n_i}\) is a cycle of order \(n_i\). If \(n_1 \geq n_2 \geq \cdots \geq n_k \geq f(t)\) then

\[R(G, tW_4) = \max_{1 \le i \le k} \left\{ n_1 + \sum_{j=i}^k l_j n_j \right\} + t - 2.\] (2)

2. The Proof of Theorem

We first show the following lemma which is used to prove Theorem 1.1.

Lemma 2.1. For positive integers n and t with \(t \leq \frac{1}{2}(\lfloor \frac{n}{2} \rfloor - 1)\). Then, \(R(C_n, tP_3) = n + t - 1\).

Proof. The graph \(K_{n-1} \cup K_{t-1}\) is \((C_n, tP_3)\)-free with n+t-2 vertices which is concludes the lower bound \(R(C_n, tP_3) \ge n+t-1\).

To obtain the upper bound \(R(C_n,tP_3) \leq n+t-1\), we use induction technique on t. The Result of Faudree et al. [7], \(R(P_l,P_3)=l\) for \(l\geq 4\), implies that the assertion holds for t=1. Let F be a graph with |F|=n+t-1 containing no \(C_n\) and then by induction on t, we have \((t-1)P_3\) in \(\overline{F}\). Let \(B=\{x_1,y_1,z_1,\ldots,x_{t-1},y_{t-1},z_{t-1}\}\) be the vertex set of (t-1) copies of \(P_3\) in \(\overline{F}\) and each of path \(P_3^i\) has edges \(x_iy_i\) and \(y_iz_i\) for \(i=1,2,\ldots,(t-1)\). Let us now consider the subgraph F[A] of F induced by \(A=V(F)\backslash B\), where V(F) is the vertex set of graph F. It is clear that the induced subgraph F[A] has order n-2t+2. Suppose on the contrary that \(\overline{F}\) contains no \(tP_3\) and hence the subgraph F[A] has minimum degree at least n-2t since otherwise the subgraph \(\overline{F}[A]\) contains \(P_3\) which together with B produce a copy of \(tP_3\) in \(\overline{F}\).

We next consider the relation between the vertices in A and in B. Note that \(\overline{F}\) does not contain \(tP_3\). Thus there are at least two vertices of each \(\{x_i,y_i,z_i\}\) adjacent to all but at most three vertices in A since otherwise we have two copies of \(P_3\) between the vertices in \(\{x_i,y_i,z_i\}\) and in A which together with \(B\setminus\{x_i,y_i,z_i\}\) forms a copy of \(tP_3\) in \(\overline{F}\). Now without loss of generality, we may assume that each \(x_i\) and \(z_i\) are adjacent to all but at most three vertices in A. Let F[D] be the subgraph of F induced by the set \(D=A\cup\{x_1,z_1,x_2,z_2,\ldots,x_{t-1},z_{t-1}\}\). Immediatelly, we obtain that F[D] has order n with minimum degree \(\delta(F[D]) \geq n-2t-1\). Since \(t \leq \frac{1}{2}(\lfloor \frac{n}{2} \rfloor -1)\), it follows that \(\delta(F[D]) \geq \frac{n}{2}\). By the result of Bondy's in Lemma 1.1 implies that F[D] contains cycle of order n in F, contradicting with our assumption on F. Hence \(\overline{F}\) contains a copy of \(tP_3\) as claimed. This concludes the proof.

In the following lemma is the weaker form of Theorem 1.1.

Lemma 2.2. Let \(t \ge 1\) be an integer and \(f(t) = 15t^2 - 4t + 2\). If F is a graph with order 2n + t - 2 containing \(C_{n-1}\) and \(n \ge f(t)\) then F contains \(C_n\) or \(\overline{F}\) contains \(tW_4\).

Proof. Let F be a graph with |F| = 2n + t - 2 containing \(C_{n-1}\). We will show that F contains \(C_n\) or \(\overline{F}\) contains \(tW_4\).

Since F contains \(C_{n-1}\), we have that the order of \(F-C_{n-1}\) is n+t-1. Note that if \(t\geq 1\) then \(n\geq f(t)>4t+2\) (this fact is equivalent with condition in Lemma 2.1), and hence Lemma 2.1 give an implication that there is \(C_n\) in \(F-C_{n-1}\) or \(tP_3\) is in the complement of \(F-C_{n-1}\). If \(F-C_{n-1}\) contains \(C_n\) then we are done. Therefore, we have cycle \(C_{n-1}\) in F and \(\overline{F}\) contains t disjoint copies \(P_3^1, P_3^2, \ldots, P_3^t\) of path with three vertices. It can be verified that there is no common vertex between \(C_{n-1}\) and \(tP_3\).

Assume that there is no \(C_n\) in F, we will find \(tW_4\) in \(\overline{F}\). Let us consider the relation between the vertices in \(A=\{x_1,x_2,\ldots,x_{n-1}\}\) and in \(B=V(P_3^1)\cup V(P_3^2)\cup\cdots\cup V(P_3^t)\). Suppose that the neighborhood \(N_A(u)\) in A of a vertex \(u\in B\) satisfies \(|N_A(u)\cap V(C_{n-1})|\geq 5t-1\). Let \(x_i,x_j\in N_A(u)\cap V(C_{n-1})\) with i< j. Note that j-i>1 since otherwise we can see that the cycle \(C_{n-1}\) including the vertex u extend to a cycle of order n. Meanwhile, if \(x_{i+1}\) and \(x_{j+1}\) are adjacent in F then we also obtain the cycle \(C_n'=x_iux_jx_{j-1}\ldots x_{i+1}x_{j+1}x_{j+2}\ldots x_{n-1}x_1x_2\ldots x_i\) of length n in F. If \(x_{i+1}x_{j+1}\) is not an edge in F for every pair \(x_i,x_j\in N_A(u)\cap V(C_{n-1})\) then the set \(\{x_{i+1},x_{j+1}\in N_A(u)\cap V(C_{n-1})\}\cup \{u\}\) is 5t independent vertices in F forming \(tW_4\) in \(\overline{F}\). Therefore, we obtain \(|N_A(u)\cap V(C_{n-1})|\leq 5t-2\) for each u in B. Thus,

\[\left| A \setminus \bigcup_{u \in B} N_A(u) \right| \ge n - 1 - 3t(5t - 2). \tag{3}\]

Note that \(n \geq f(t)\), and so the equation (3) implies that the set A contains at least 2t+1 vertices which are not adjacent to all vertices in B and then will form \(tW_4\) in \(\overline{F}\). This completes the proof of Lemma 2.2.

In the rest, we are now ready to give the proof of Theorem 1.1 as the main result.

Proof of Theorem 1.1. Immediately we can verified that the graph \(2K_{n-1} \cup K_{t-1}\) is \((C_n, tW_4)\)—free on 2n + t - 3 vertices to give the lower bound \(R(C_n, tW_4) \ge 2n + t - 2\).

By using induction on t, we will show the upper bound \(R(C_n, tW_4) \leq 2n + t - 2\). From Theorem 1.2, we have \(R(C_n, W_4) = 2n - 1\) for \(n \geq 3\). Note that if t = 1 then \(n \geq f(1) > 3\). Therefore, Theorem 1.1 is true for \(n \geq f(1) \geq 3\). In what follows we assume \(t \geq 2\) and Theorem 1.1 is also holds for \(n \geq f(t-1)\), that is \(R(C_n, (t-1)W_4) \leq 2n + t - 3\).

We are now show that Theorem 1.1 is also valid for \(n \geq f(t)\). Let F be a graph with |F| = 2n + t - 2. We shall show that there is a \(C_n\) in F or \(tW_4\) is in \(\overline{F}\). Note that if \(t \geq 1\) then \(n \geq f(t) > 3\) and then by Theorem 1.2 in Surahmat et al. [14] we have that there is a \(C_n\) in F or \(\overline{F}\) contains \(W_4\). Then the proof is end, if we have \(C_n\) in F. Thus we have \(W_4\) in \(\overline{F}\). Hence, \(|F - W_4| = 2(n-2) + (t-1) - 2\) and by induction on t note that \(n-1 \geq f(t) - 1 > f(t-1)\), we obtain \(C_{n-2}\) in \(F - W_4\) or \((t-1)W_4\) in the complement of \(F - W_4\). Meanwhile, if there is a graph \((t-1)W_4\) in the complement of \(F - W_4\) then together with the first one will forms \(tW_4\) in \(\overline{F}\) and we are done. Thus F has a cycle \(C_{n-2}\) and \(|F - C_{n-2}| = n + t\). Note that if \(t \geq 1\) then

\(n \ge f(t) > 4t + 2\), and by Lemma 2.1 we obtain \(C_n\) in \(F - C_{n-2}\) or \(tP_3\) is in the complement of \(F - C_{n-2}\). If \(F - C_{n-2}\) contains \(C_n\) then we are done.

Thus, we have \(C_{n-2}\) in F and \(\overline{F}\) contains t disjoint copies \(P_3^1, P_3^2, \ldots, P_3^t\) of path with three vertices. It is clear that the subgraphs \(C_{n-2}\) and \(tP_3\) has no vertices in common.

Assume that there is no \(C_{n-1}\) in F. We will show that \(\overline{F}\) contains \(tW_4\). Let us now focus to see the relation between the vertices in A and in B; where \(A=\{x_1,x_2,\ldots,x_{n-2}\}\) is the vertex set of cycle \(C_{n-2}\) and \(B=V(P_3^1)\cup V(P_3^2)\cup\cdots\cup V(P_3^t)\). Suppose that the neighborhood \(N_A(u)\) in A of a vertex \(u\in B\) satisfies \(|N_A(u)\cap V(C_{n-2})|\geq 5t-1\). Let \(x_i,x_j\in N_A(u)\cap V(C_{n-2})\) with i< j. Note that j-i>1 since otherwise \(C_{n-2}\) together with the vertex u forms a cycle of order n-1. Therefore, Lemma 2.2 implies that \(\overline{F}\) contains \(tW_4\). If \(x_{i+1}\) and \(x_{j+1}\) are adjacent in F then we get the cycle \(C'_{n-1}=x_iux_jx_{j-1}\ldots x_{i+1}x_{j+1}x_{j+2}\ldots x_{n-2}x_1x_2\ldots x_i\) of length n-1 in F, and then by Lemma 2.2 we obtain a copy of \(tW_4\) in \(\overline{F}\). If \(x_{i+1}x_{j+1}\) is not an edge in F for every pair \(x_i,x_j\in N_A(u)\cap V(C_{n-2})\) then the set \(\{x_{i+1},x_{j+1}\in N_A(u)\cap V(C_{n-2})\}\cup\{u\}\) contains 5t vertices which is independent in F and so forms \(tW_4\) in \(\overline{F}\). Hence, we find \(|N_A(u)\cap V(C_{n-2})|\leq 5t-2\) for each u in B. Therefore,

\[\left| A \setminus \bigcup_{u \in B} N_A(u) \right| \ge n - 2 - 3t(5t - 2). \tag{4}\]

By subtitution of condition \(n \ge f(t)\) to the equation (4) give an implication that the set A contains at least 2t vertices which are not adjacent to all vertices in B and hence \(\overline{F}\) contains \(tW_4\). This concludes that F has \(C_{n-1}\) or \(\overline{F}\) has \(tW_4\). If we have \(tW_4\) in \(\overline{F}\) then the proof is done. Therefore, we have a copy of cycle \(C_{n-1}\) in F. Now, by Lemma 2.2 we obtain a copy of \(C_n\) in F or a copy of \(tW_4\) in \(\overline{F}\). The proof of Theorem 1.1 is now complete.

To the rest of this paper, let us present the conjecture as an open problem to further work on to the readers. By regarding Theorem 1.1, we believe that the following conjecture is true.

Conjecture 1. For \(t \ge 1\) and \(m \ge 4\), there exists \(n_0 = f(t, m)\) such that if \(n \ge n_0\) then the cycle \(C_n\) is \(tW_m\)-good.

3. Remark and Conclusion

In the rest of paper, we state the new result corresponding to the goodness of cycle \(C_n\) with respect to \(tW_4\). In addition, if G is a disjoint union of cycles then we also obtain the exact value of Ramsey number \(R(G, tW_4)\). This work is an effort to have a result of the Ramsey numbers \(R(C_n, tW_m)\) and \(R(G, tW_m)\) for any positive integers t, n and m. In future, it is not only possible obtaining the new technic to prove the clasical Ramsey number in two colors but also a wide multi colors Ramsey number in general as well.

Acknowledgement

The author would like to thank the reviewers for valueable comments of this manuscript.

References

• [1] E.T. Baskoro, Hasmawati, and H. Assiyatun, Note. The Ramsey Number for Disjoint Unions of Trees, Discrete Math., 306 (2006), 3297–3301.
• [2] H. Bielak, Ramsey numbers for a disjoint union of good graphs, Discrete Math., 310 (2010), 1501–1505.
• [3] J.A. Bondy, Pancyclic graph, J. Combin. Theory Ser. B, 11 (1974), 80–84.
• [4] S.A. Burr, Ramsey numbers involving long suspended paths, J. Lond. Math. Soc., 24 (2) (1981), 405–413.
• [5] Y. Chen, Y. Zhang, and K. Zhang, The Ramsey number of stars versus wheels, European J. Combin., 25 (2004), 1067–1075.
• [6] Y. Chen, Y. Zhang and K. Zhang, The Ramsey number paths versus wheels, Discrete Math., 290 (2005), 85–87.
• [7] R.J. Faudree, S.L. Lawrence, T.D. Parsons, and R.H. Schelp, Path-Cycle Ramsey numbers, Discrete Math., 10 (1974), 269–277.
• [8] S.P. Radziszowski, Small Ramsey Numbers, Electron. J. Combin., DS1.12 (2019), http://www.combinatorics.org.
• [9] V. Rosta, Ramsey theory applications, Electron. J. Combin., DS1.13 (2019), http://www.combinatorics.org.
• [10] S. Stahl, On the Ramsey number r(F, Km) Where F is a Forest, Canad. J. Math., 27 (1975), 585–589.
• [11] I W. Sudarsana, On the Ramsey number for cycle with respect to identical copies of complete graphs, J. Combin. Math. Combin. Comput., 99 (2016), 61-68.
• [12] I W. Sudarsana, The goodness of long path with respect to multiple copies of small wheel, Far East Journal of Mathematical Sciences, 59 (1) (2011), 47–54.
• [13] I W. Sudarsana, E.T. Baskoro, H. Assiyatun, and S. Uttunggadewa, On the union of graphs Ramsey numbers, Appl. Math. Sci., 8 (16) (2014), 767-773.
• [14] Surahmat, E.T. Baskoro, and I. Tomescu, The Ramsey numbers of large cycles versus wheels, Discrete Math., 306 (2006), 3334–3337.