The Ramsey Number for Tree Versus Wheel with Odd Order

Abstract

Chen et al. (Appl Math Lett 17:281–285, 2004) conjectured that for even m, $R(T_n,W_m)=2n-1$ if the maximum degree $\varDelta (T_n)$ is small. However, they did not state how small it is. Related to this conjecture, it is also interesting to know which tree $T_n$ causes the Ramsey number $R(T_n,W_m)$ to be greater than $2n-1$ whenever m is even. In this paper, we determine the Ramsey number $R(T_n,W_8)$ for all trees $T_n$ with $\varDelta (T_n) \ge n-3$. For most cases of these trees, $R(T_n,W_8) > 2n-1$. Furthermore, we also prove that for certain values of n, the Ramsey number $R(T_n,W_m)$ is greater than $2n-1$ if $\varDelta (T_n) \ge n-3$ and m is even. Finally, we refine the above conjecture by giving an upper bound on the maximum degree of the tree $T_n$.

1 Introduction

For given graphs G and H, a graph F is called (G, H)-good if F contains no G and $\overline{F}$ contains no H. Any (G, H)-good graph on n vertices is called (G, H, n)-good. The Ramsey number R(G, H) is defined as the smallest positive integer n such that no (G, H, n)-good graph exists. Chvátal and Harary [9] studied the Ramsey number for general graphs and established the lower bound: $R(G,H)\ge (\chi (H)-1)(c(G)-1)+1$, where c(G) is the order of the largest component of G, and $\chi (H)$ is the chromatic number of H.

Let $T_n$ be a tree, namely a connected graph on n vertices with no cycle. Let $W_m$ be a wheel on $m+1$ vertices that consists of a cycle $C_m$ with one additional vertex being adjacent to all vertices of $C_m$. If $G=T_n$, $H=W_m$ and $n \ge m \ge 3$, we obtain that $R(T_n,W_m)\ge 2n-1$ for even m, and $R(T_n,W_m)\ge 3n-2$ for odd m.

The study of the Ramsey number $R(T_n,W_m)$ has been extensively investigated. However, the results are still far from satisfactory. For any star $S_n$, the value of $R(S_n,W_m)$ is not always equal to the Chvátal–Harary bound [7, 10, 11, 19, 20], but for trees $T_n$ other than a star and $S_n(1,2)$, all the known Ramsey numbers $R(T_n,W_m)$ are equal to the Chvátal–Harary bound [1, 4,5,6, 8, 12, 17]. For other pairs of graphs G and H, some results on their Ramsey numbers R(G, H) can be seen in, for instances, [13,14,15,16] and [18].

Y. Chen, Y. Zhang, and K. Zhang (2004) strongly conjectured that $R(T_n,$ $W_m)=2n-1$ if the maximum degree of $T_n$ is small and m is even. However, they did not specify how small the maximum degree is. In this paper, we shall determine the Ramsey number $R(T_n,W_8)$ for all trees $T_n$ of order n such that the maximum degree of $T_n$ is at least $n-3$. Furthermore, we also prove that for certain values of n, the Ramsey number $R(T_n,W_m)$ is greater than $2n-1$ if $\varDelta (T_n) \ge n-3$ and m is even. In fact, these Ramsey numbers are the function of both m and n. Finally, we refine the above conjecture by giving an upper bound on the maximum degree of the tree $T_n$.

In general, we will follow the terminology used in [2]. Let G(V, E) be a graph. For $U\subseteq V(G)$, let G[U] be the induced subgraph of G by U; that is the maximal subgraph of G with the vertex set U. For $v\in V(G)$ and $U,W\subseteq V(G)$, we denote $N_U(v)=\{u\in U : uv\in E(G) \}$, and E(U, W) as the set of the edges between U and W. The degree of a vertex $v\in V(G)$, denoted by $\deg (v)$, is $|\{u\in V(G): vu \in E(G)\}|$. The maximum degree of graph G is $\max \{\deg (v): v \in V(G)\}$ and it is denoted by $\varDelta (G)$. Similarly, the minimum degree of graph G is defined as $\min \{\deg (v): v \in V(G)\}$ and denoted by $\delta (G)$. We use kG to denote the disjoint union of k copies of G. By using the same notation in [4], denote by $S_n(l,m)$ a tree of order n obtained from $S_{n-m\times l}$ by subdividing each of l chosen edges m times, and denote by $S_n(l)$ a tree of order n obtained from a star $S_l$ and $S_{n-l}$ by adding an edge joining their centers. We also define the hub vertex of $S_n(l,m)$ as the center vertex of $S_{n-m\times l}$, and the hub vertex of $S_n(l)$ as the center of $S_{n-l}$.

2 The Ramsey number $R(T_n,W_m)$

Related to the conjecture proposed by Chen et al. [4], it is interesting to know for which tree $T_n$ we have that $R(T_n,W_m)>2n-1$ for even m. The first main result deals with the Ramsey number $R(T_n,W_8)$ for all trees $T_n$ with $\varDelta (T_n)\ge n-3$ other than a star, as stated in Theorem 1. In the second main results (Theorems 2, 3 and 4), we derive a general lower bound for $R(T_n,W_m)$ for trees $T_n$ with large maximum degree and even m. This lower bound is a function of both m and n. These results show that $R(T_n,W_m) > 2n-1$ for such trees and even m. The third main result discusses the conjecture given by Chen et al. We refine this conjecture by providing the condition of small maximum degree for tree $T_n$.

Let us consider any tree $T_n$ of order n such that the maximum degree $\varDelta (T_n)$ is at least $n-3$. Then, this tree $T_n$ will be isomorphic to either $S_n$, $S_n(1,1)$, $S_n(1,2)$, $S_n(2,1)$, or $S_n(3)$. The Ramsey number for such a tree $T_n$ other than a star versus a wheel $W_8$ on nine vertices is given in the following theorem.

Theorem 1

The Ramsey number $R(T_n,W_8)$ of a tree $T_n$ on n vertices other than a star with $\varDelta (T_n)\ge n-3$ versus a wheel on nine vertices is given below:

• $R(S_n(1,1),W_8)={\left\{ \begin{array}{ll} 2n,\ n\equiv 0\ (\text {mod}\ 2)\\ 2n+1,\ n\equiv 1\ (\text {mod}\ 2) \end{array}\right. }; \ n\ge 5$

• $R(S_n(1,2),W_8)={\left\{ \begin{array}{ll} 2n,\ n\not \equiv 3\ (\text {mod}\ 4)\\ 2n+1,\ n\equiv 3\ (\text {mod}\ 4) \end{array}\right. }; \ n\ge 8$

• $R(S_n(2,1),W_8)={\left\{ \begin{array}{ll} 2n-1,\ n\equiv 1\ (\text {mod}\ 2)\\ 2n,\ n\equiv 0\ (\text {mod}\ 2) \end{array}\right. }; \ n\ge 8$

• $R(S_n(3),W_8)={\left\{ \begin{array}{ll} 2n-1,\ n\equiv 1\ (\text {mod}\ 2)\\ 2n,\ n\equiv 0\ (\text {mod}\ 2) \end{array}\right. }; \ n\ge 8.$

The proof of Theorem 1 will be given in Sect. 3. Note that $R(S_n,W_8)$ has been given by Zhang et al. [19, 20], see Theorems 5 and 6.

It has been shown in [4] that $R(S_n(1,1),W_m)$ is a function of both m and n, for even m. Precisely, $R(S_n(1,1),W_m) \ge 2n+\frac{m}{2}-3$ for even m and $n=k\frac{m}{2}+3$ for any integer $k\ge 2$. It is natural that the values of $R(S_n(1,2),W_m)$, $R(S_n(2,1),W_m)$, and $R(S_n(3),W_m)$ also depend on both m and n.

For even $m\ge 8$, and $n\equiv 4\; (\text {mod}\ \frac{m}{2})$, consider the graph $G=\overline{H}\cup K_{n-1}$ with $H=(\frac{2n+m-8}{m})K_{\frac{m}{2}}$. Then, it is easy to see that G is a $(T_n,W_m,2n+\frac{m}{2}-5)$-good graph for any tree $T_n$ on n vertices with $\varDelta (T_n)\ge n-3$. Hence, we have the following theorem.

Theorem 2

For any tree $T_n$ on n vertices with $\varDelta (T_n)=n-3$, $n\equiv 4 \;(\text {mod}\ \frac{m}{2})$ and even $m\ge 8$, $R(T_n,W_m)\ge 2n+\frac{m}{2}-4$.

Moreover, if we use $H=K_{\frac{m}{2}-1,\frac{m}{2}-1}\cup (\frac{2n-4}{m})K_{m/2}$ for the graph $G=\overline{H}\cup K_{n-1}$ and $n\equiv 2 \;(\text {mod}\ m/2)$, then it is easy to see that G is a $(T,W_m,2n+\frac{m}{2}-5)$-good graph for any tree T on n vertices with $\varDelta (T)\ge n-3$. Hence, we have the following theorem.

Theorem 3

For any tree $T_n$ on n vertices with $\varDelta (T_n)=n-3$, $n\equiv 2 \;(\text {mod}\ m/2)$ and even $m\ge 8$, $R(T_n,W_m)\ge 2n+\frac{m}{2}-4$.

For even m and $1\le t\le m/2-2$, we can get a lower bound for $R(S_n(1,2t),W_m)$ by defining $G=\overline{H}\cup K_{n-1}$ with $H=(\frac{2n+m-2t-4}{m})K_{m/2}$ for $n\equiv t+2 \;(\text {mod}\ m/2)$. Since G is an $(S_n(1,2t),W_m,2n+m/2-t-3)$-good graph, we have the following theorem.

Theorem 4

For $n\equiv t+2 \;(\text {mod}\ m/2)$ and even $m\ge 8$, $R(S_n(1,2t),W_m)\ge 2n+\frac{m}{2}-t-2$.

For $t=1$, Theorem 4 gives a better lower bound for $R(S_n(1,2),W_m)$ compared to Theorem 2.

Corollary 1

For $n\equiv 3 \;(\text {mod}\ m/2)$ and even $m\ge 8$, $R(S_n(1,2),W_m)\ge 2n+\frac{m}{2}-3$.

In [1], it is conjectured that for every tree $T_n$ other than a star and $n>m$, the Ramsey number $R(T_n,W_m)$ is equal to the Chvátal–Harary bound ($R(T_n,W_m)=2n-1$ for even $m \ge 6$, and $R(T_n,W_m)=3n-2$ for odd $m\ge 7$). For odd m, the conjecture is true for $n\ge \frac{m+1}{2}\ge 3$ [10] and for all ES trees which is believed to be all trees [17]. However, the conjecture must be refined for even m, see Theorem 1 and [4]. In 2004, Chen et al. believed that the conjecture is true for even m if $T_n$ has a small maximum degree. However, they did not specify how small the maximum degree is. Here, we provide a refinement of the conjecture by giving the condition of the maximum degree.

Conjecture 1

If $T_n$ is a tree on n vertices with $\varDelta (T_n)\le n-m+2$, then $R(T_n,W_m)=2n-1$ provided m is even and $n> m\ge 4$.

The conjecture is true for $m=4$ [1] and $m=6$ [5, 6, 8]. If this conjecture is true, then this upper bound is the best possible one since Theorem 4 gives the following corollary.

Corollary 2

For $n\equiv 0 \;(\text {mod}\ m/2)$ and even $m\ge 8$, we have that $\varDelta (S_n(1,m-4))= n-m+3$ and $R(S_n(1,m-4),W_m)\ge 2n$.

3 Proof of Theorem 1

We will use some known Ramsey numbers and the following lemmas to prove Theorem 1:

Theorem 5

[19] $R(S_n,W_8)=2n+2,\ \text {for even}\ n\ge 6$.

Theorem 6

[20] $R(S_n,W_8)=2n+1,\ \text {for odd}\ n\ge 5$.

Lemma 1

[4] If G is a graph of order $n\ge 6$ with $\delta (G)\ge n-3$, then G contains $S_n(3)$ and $S_n(2,1)$.

Lemma 2

Let G be a graph of order 2n, $n\ge 8$. If G contains $S_n(1,1)$ and $\overline{G}$ contains no $W_8$, then G must contain $S_n(1,2)$, $S_n(2,1)$ and $S_n(3)$.

Proof

Let G be a graph satisfying the assumptions above. Let $\{u_0,u_1,\ldots ,u_{n-1}\}$ be the set of the vertices of $S_n(1,1)$ in G with $u_0$ as the hub vertex and $u_0 u_1,u_1 u_{n-1}\in E(G)$. Let $W=\{w_1,w_2,\ldots ,w_n\} = V(G)-\{u_0,u_1,\ldots ,u_{n-1}\}$ and $U=\{u_2,u_3,\ldots ,u_{n-2}\}$.

First, we prove that G contains $S_n(2,1)$. Assume G contains no $S_n(2,1)$, then $E(U,W)=\emptyset$ and $E(G[U])=\emptyset$. This implies that $\overline{G}[w_1,w_2,w_3,w_4,u_2,u_3,u_4,u_5,u_6]$ contains a $W_8$ with $u_6$ as the center and $w_1u_2w_2u_3w_3u_4w_4u_5w_1$ as the cycle, a contradiction.

Next we prove that G contains $S_n(3)$. Assume G contains no $S_n(3)$, then $N(u_1)=\{u_0,u_{n-1}\}$ and $|N_W(u_i)|\le 1$ for $i \in [2,n-2]$. Since $E(U,W)\le n-3$ and $|W|=n\ge 8$, there exist $w^1,w^2,w^3,w^4\in W$ with $|N_U(w^i)|\le 1$ for $i=1,2,3,4$. This means that the subgraph of $\overline{G}$ induced by $\{u_1,u_2,u_3,u_4,u_5,w^1,$ $w^2,w^3,w^4\}$ contains a $W_8$ with $u_1$ as the center, a contradiction.

Finally we prove that G contains $S_n(1,2)$. Assume G contains no $S_n(1,2)$, then $N(u_{n-1})\subseteq \{u_0,u_1\}$ and $|N_U(w)|\le 1$ for each vertex $w\in W$. If there is a vertex in U with at least three neighbors in W, say $\{w_1,w_2,w_3\}\subseteq {N_W(u_2)}$, then $\overline{G}[u_3,u_4,u_5,u_6,u_{n-1},w_1,w_2,w_3,w_4]$ contains a $W_8$ with $u_{n-1}$ as the center, a contradiction. If there is no vertex in U with at least three neighbors in W, then any four vertices in U and any four vertices in W together with $u_{n-1}$ will induce a $W_8$ in $\overline{G}$ with $u_{n-1}$ as the center, a contradiction. $\square$

Lemma 3

If G be a graph of order $n\ge 9$ with $\delta (G)\ge n-4$ and $\varDelta (G)\ge n-3$, then G contains $S_n(3)$ and $S_n(2,1)$.

Proof

Let $V(G)=\{w_1,w_2,\ldots ,w_n\}$ and $w_1$ be a vertex with degree at least $n-3$ and $w_4,w_5,\ldots ,w_n\in N(w_1)$. First, we prove that G contains an $S_n(3)$. If $w_2,w_3\notin N(w_1)$ or $w_2w_3\notin E(G)$, then since $\delta (G)\ge n-4$ and $n\ge 9$, $|N(w_1)\cap N(w_2)|+|N(w_1)\cap N(w_3)|\ge n-5 + n-5 \ge n-2$ which implies $N(w_1)\cap N(w_2)\cap N(w_3)\ne \emptyset$, and hence, G contains an $S_n(3)$. Otherwise, without loss of generality $w_2\in N(w_1)$ and $w_2w_3\in E(G)$. Since $\delta (G)\ge n-4$ and $n \ge 9$, we have $\deg (w_2)\ge 5$ which implies $N(w_1)\cap N(w_2)\ne \emptyset$, and hence, G contains an $S_n(3)$.

Next, we prove G contains an $S_n(2,1)$. Since $\delta (G)\ge n-4$ and $n \ge 9$, we have $\deg (w_i)\ge 5$ for all i. Therefore, $|N(w_1)\cap N(w_2)|\ge 3$ and $|N(w_1)\cap N(w_3)|\ge 3$. It follows that G contains an $S_n(2,1)$. $\square$

3.1 Proof of Theorem 1

We will divide Theorem 1 into smaller theorems and prove each of them separately.

Theorem 7

$R(S_n(1,1),W_8)=2n+1$ for odd $n \ge 5$.

Proof

Let us consider the graph $G=\overline{(\frac{n+1}{4})K_4}\cup K_{n-1}$, for $n\equiv 3(\text {mod}\ 4)$ and $G=\overline{K_{3,3}\cup (\frac{n-5}{4})K_4}$ $\cup K_{n-1}$, for $n\equiv 1(\text {mod}\ 4)$. G is a $(S_n(1,1),W_8,2n)$-good graph, and thus, we have $R(S_n(1,1),W_8)$ $\ge 2n+1$ for odd n.

In order to show that $R(S_n(1,1),W_8) \le 2n+1$ for odd $n \ge 5$, suppose there is a graph G of order $2n+1$ containing no $S_n(1,1)$ and $W_8\not \subseteq \overline{G}$. First, we will show that G must contain an $S_{n-1}$. In the case of $n\ge 7$, by Theorem 5 we obtain $R(S_{n-1},W_8)=2(n-1)+2=2n$ for odd $n\ge 7$. Since $\overline{G}$ contains no $W_8$, then G must contain an $S_{n-1}$.

Now, consider if $n=5$. For a contradiction, assume that G contains no $S_4$. Then, it implies that $\varDelta (G)\le 2$, and so $\delta (\overline{G})\ge 8$. Now, consider the graph $\overline{G}$. Let v be a vertex in $\overline{G}$ and let $A=\{v_1,v_2,\ldots ,v_8\}\subseteq N_{\overline{G}}(v)$. Every vertex in A has at least eight neighbors in $\overline{G}$. Since there are only three vertices in $\overline{G}$ that are not in A, then every vertex in $\overline{G}[A]$ has at least five neighbors in $\overline{G}[A]$, so $\varDelta (\overline{G}[A])\ge 5$. In [3], Bondy showed that if a graph $G_1$ with $n_1$ vertices have $\delta (G_1)\ge n_1/2$, then $G_1$ contains a cycle of any order less or equal to $n_1$ or $G_1=K_{n_1/2,n_1/2}$ for even $n_1$. Therefore, $\overline{G}[A]$ contains a $C_8$ or $\overline{G}[A]=K_{4,4}$. Since $K_{4,4}$ contains a $C_8$, then $\overline{G}$ contains a $W_8$, a contradiction. Hence, G contains an $S_{n-1}$ (for $n=5$).

Let $U=\{u_0, u_1,u_2,\ldots ,u_{n-2}\}$ be the set of vertices of $S_{n-1}$ in G with $u_0$ as the center. Let $W=\{w_1,w_2,\ldots ,w_{n+2}\}$ be the set of all vertices in $V(G)-U$. Since G contains no $S_n(1,1)$, then $E(U,W)=\emptyset$. Now, consider the following two cases.

Case 1. $\delta (G[W])\le n-3$. Let $\deg _{G[W]}(w_1)=\delta (G[W])\le n-3$, since $|W|=n+2$, then $\deg _{\overline{G}[W]}(w_1)\ge 4$. Let $\{w_2,w_3,w_4,w_5\}\subseteq N_{\overline{G}[W]}(w_1)$. Then, the induced subgraph in $\overline{G}$ by $\{u_1$, $u_2$, $u_3$, $u_4$, $w_1$, $w_2$, $w_3$, $w_4$, $w_5\}$ will contain a $W_8$ with $w_1$ as the center, a contradiction.

Case 2. $\delta (G[W])\ge n-2$. Let $\{w_2,w_3,\ldots ,w_{n-1}\}\subseteq N_G(w_1)$. Since $n\ge 5$ and $\delta (G[W])\ge n-2$, $w_n$ has at least three neighbors in G[W], which means $w_n$ have a neighbor in $N_G(w_1)$, which makes an $S_n(1,1)$ in G[W], a contradiction. $\square$

Theorem 8

$R(S_n(1,1),W_8)=2n$ for even $n \ge 6$.

Proof

Consider the graph $G=K_{4,4}\cup K_{n-1}$ for $n=8$ and $G=\overline{C}_n\cup K_{n-1}$ for $n\ne 8$. Then, G contains no $S_n(1,1)$ and its complement contains no $W_8$. Hence, $R(S_n(1,1),W_8) \ge 2n$.

Now, to show that $R(S_n(1,1),W_8) \le 2n$ for even $n \ge 6$, consider any graph G of order 2n containing no $S_n(1,1)$ and $W_8\not \subseteq \overline{G}$.

By Theorem 6, we obtain that $R(S_{n-1},W_8)=2(n-1)+1=2n-1$ for even n. Since $\overline{G}$ contains no $W_8$, then G contains an $S_{n-1}$. Let $U=\{u_0, u_1,u_2,\ldots ,u_{n-2}\}$ be the set of vertices of $S_{n-1}$ in G with $u_0$ as the center. Let $W=\{w_1,w_2,\ldots ,w_{n+1}\}$ be the set of all vertices in $V(G)-U$. Since G contains no $S_n(1,1)$, then $E(U,W)=\emptyset$. Now, consider the following cases.

Case 1. $\delta (G[W])\le n-4$. Let $\deg _{G[W]}(w_1)=\delta (G[W])\le n-4$. Since $|W|=n+1$, then $\deg _{\overline{G}[W]}(w_1)\ge 4$. Let $\{w_2,w_3,w_4,w_5\}\subseteq N_{\overline{G}[W]}(w_1)$, then the induced subgraph in $\overline{G}$ by $\{u_1,u_2,u_3,u_4,w_1,w_2,$ $w_3,w_4,w_5\}$ will contain a $W_8$ with $w_1$ as the center, a contradiction.

Case 2. $\delta (G[W])\ge n-3$. If G[W] has a vertex of degree at least $n-2$, say $w_1$, and let $N_G(w_1)=\{w_2,w_3,\ldots ,w_{n-1}\}$. Since $n\ge 6$ and $\delta (G[W])\ge n-3$, $w_n$ has at least three neighbors in G[W]. Hence, one of neighbors of $w_n$ is in $N_G(w_1)$ and it produces an $S_n(1,1)$ in G[W], a contradiction. Therefore, G[W] must be $(n-3)$-regular. But, this is not possible since the order of G[W] is odd, a contradiction.

Corollary 3

Let G be a graph of order 2n containing no $S_n(1,1)$ with $n \ge 6$. If $\overline{G}$ contains no $W_8$, then n is odd and $G=G_1 \cup G_2$ with $G_1$ being a graph of order $n-1$ and $G_2$ being a regular graph of degree $n-3$.

Proof

Let G be a graph of order 2n satisfying the assumptions above. By Theorem 8, n must be odd. Theorem 5 states that $R(S_{m-1},W_8)=2m$ for odd m. Since $\overline{G}$ contains no $W_8$ and $|V(G)|=2n$, then G must contain $S_{n-1}$ by Theorem 5. Now, by a similar argument as in the proof of Theorem 8, we obtain $G=G_1 \cup G_2$ with $G_1$ is a graph of order $n-1$ and $G_2$ is a regular graph of degree $n-3$.

Theorem 9

$R(S_n(1,2),W_8)=R(S_n(2,1),W_8)=R(S_n(3),W_8)=2n$ for even $n \ge 8$.

Proof

Consider $G=\overline{(\frac{n}{4})K_4}\cup K_{n-1}$ for $n\equiv 0 \;(\text {mod}\ 4)$ and $G=\overline{K_{3,3}\cup (\frac{n-6}{4})K_4}\cup K_{n-1}$ for $n\equiv 2(\text {mod}\ 4)$. Then, G contains no tree T on n vertices with $\varDelta (T)\ge n-3$ and its complement contains no $W_8$. Hence, we have $R(S_n(1,2),W_8)\ge 2n$, $R(S_n(2,1),W_8)\ge 2n$, and $R(S_n(3),W_8)\ge 2n$ for even n.

Now, for even $n\ge 8$, let G be a graph of order 2n and assume $\overline{G}$ contains no $W_8$. By Theorem 8, G contains $S_n(1,1)$. By Lemma 2, G contains $S_n(1,2)$, $S_n(2,1)$, and $S_n(3)$. Hence, $R(S_n(1,2),W_8)=R(S_n(2,1),W_8)=R(S_n(3),W_8)=2n$ for even $n \ge 8$. $\square$

Theorem 10

$R(S_n(1,2),W_8)=2n+1$ for $n \ge 11$ and $n\equiv 3\;(\text {mod}\ 4)$.

Proof

If $G=\overline{(\frac{n+1}{4})K_4}\cup K_{n-1}$, then G contains no $S_n(1,2)$ and its complement contains no $W_8$. Hence, we have $R(S_n(1,2),W_8)\ge 2n+1$ for $n\equiv 3 \;(\text {mod}\ 4)$. Now, for any $n\ge 7$ and $n\equiv 3 \;(\text {mod}\ 4)$, let G be a graph of order $2n+1$ and assume $\overline{G}$ contains no $W_8$. By Theorem 7, G contains an $S_n(1,1)$. By Lemma 2, G contains $S_n(1,2)$. Hence, $R(S_n(1,2),W_8)=2n+1$ for $n \ge 11$ and $n\equiv 3 \;(\text {mod}\ 4)$. $\square$

Theorem 11

$R(S_n(1,2),W_8)=2n$ for $n \ge 9$ and $n\equiv 1 \;(\text {mod}\ 4)$.

Proof

Let $G=\overline{3C_3\cup (\frac{n-9}{4})K_4}\cup K_{n-1}$. Then, G contains no $S_n(1,2)$ and its complement has no $W_8$. Hence, we have $R(S_n(1,2),W_8)\ge 2n$ for $n\equiv 1 \;(\text {mod}\ 4)$. Now, for any $n\ge 9$ and $n\equiv 1 \;(\text {mod}\ 4)$, assume that G is a graph of order 2n containing no $S_n(1,2)$ and $\overline{G}$ contains no $W_8$.

If G contains $S_n(1,1)$, then by Lemma 2, G contains an $S_n(1,2)$, a contradiction. Therefore, G contains no $S_n(1,1)$. By Corollary 3, we have $G= G_1 \cup G_2$, where $G_1$ is a graph of order $n-1$ and $G_2$ is an $(n-3)$-regular graph of order $n+1$. Let $V(G_2)=\{w_1,w_2,\ldots ,w_{n+1}\}$ and $N(w_1)=\{w_2,w_3,\ldots ,w_{n-2}\}$. For any $i \in \{n-1,n,n+1\}$, $N(w_i)\cap N(w_1)\ne \emptyset$ because $n\ge 9$. If $w_iw_j \in E(G)$ for any $i,j \in \{n-1,n,n+1\}$, then $G_2$ contains an $S_n(1,2)$. Therefore, the subgraph induced by $\{w_1,w_{n-1},w_n,w_{n+1}\}$ is isomorphic to $\overline{K_4}$. Since $w_1$ is arbitrary and $\overline{ G_2}$ is 3-regular, then $\overline{G_2}=\left( \frac{n+1}{4}\right) K_4$ and $|G_2|$ must be a multiple of 4. But, this is not possible since $|G_2|=n+1\equiv 2(\text {mod}\ 4)$.

Theorem 12

$R(S_n(2,1),W_8)=R(S_n(3),W_8)=2n-1$ for odd $n \ge 9$.

Proof

Consider $G=2K_{n-1}$, G contains no tree of order n and its complement contains no $W_8$. Hence, we have $R(S_n(2,1),W_8)\ge 2n-1$ and $R(S_n(3),W_8)\ge 2n-1$. Now for any odd integer $n\ge 9$, let G be a graph of order $2n-1$ and assume $\overline{G}$ contains no $W_8$. We will prove that G contains an $S_n(2,1)$ and an $S_n(3)$. From Theorem 6, G contains an $S_{n-2}$. Now, consider the following cases.

Case 1. $\varDelta (G)\ge n-2$. Let $u_0$ be a vertex with degree $\varDelta (G)\ge n-2$. Let $U=\{u_1,u_2,\ldots ,u_{n-2}\}\subseteq N(u_0)$, and $W=V(G)-(U\ \cup \{u_0\})=\{w_1,w_2,\ldots ,w_n\}$.

Subcase 1.1. $E(U,W)=\emptyset$. If $\delta (G[W])\le n-5$, then $\varDelta (\overline{G}[W])\ge 4$. Let $w_1$ be a vertex with degree $\delta (G[W])\le n-5$ and $w_2,w_3,w_4,w_5\notin N(w_1)$. Then, there will be a $W_8$ in $\overline{G}$ with $w_1$ as its center and $u_1,u_2,u_3,u_4,w_2,w_3,w_4,w_5$ as its cycle, a contradiction. Therefore, $\delta (G[W])\ge n-4$. Note that G[W] cannot be $(n-4)$-regular since n is odd; then, there is a vertex of degree at least $n-3$ in G[W]. Therefore, G[W] contains an $S_n(3)$ and $S_n(2,1)$ by Lemma 3.

Subcase 1.2. $E(U,W)\ne \emptyset$. Let $u_1w_1\in E(G)$, $U'=U-\{u_1\}$, and $W'=W-\{w_1\}$. First, assume G contains no $S_n(2,1)$. Since G contains no $S_n(2,1)$, then $E(G[U'])=\emptyset$ and $E(U',W')=\emptyset$. If $\delta (G[W])\ge n-3$, then G[W] contains an $S_n(2,1)$ by Lemma 1, so $\delta (G[W])\le n-4$. Now, consider the following subcases:

• (a) If $|N_U(w_1)|\ge 2$, let $\{u_1,u_{n-2}\}\subseteq N_U(w_1)$. Then, $N(u_1)\subseteq \{u_0,u_{n-2},w_1\}$, since otherwise G contains an $S_n(2,1)$. Since $E(U',W')=\emptyset$, then $\overline{G}$ will contains a $W_8$ with $u_1$ as the center and $u_2,u_3,u_4,u_5,w_2,w_3,w_4,w_5$ forms its cycle, a contradiction;

• (b) If $N_U(w_1)=\{u_1\}$. Let w be a vertex in G[W] with degree $\delta (G[W])\le n-4$ and $w^1,w^2,w^3\notin N_{G[W]}(w)$. Then, again in $\overline{G}$ we will have a $W_8$ with center w and cycle $w^1u_2w^2u_3w^3u_4u_5u_6w^1$, a contradiction. Note that it does not matter if $w=w_1$. Therefore, in any case G will contain an $S_n(2,1)$.

Next, assume G contains no $S_n(3)$, then $N(u_1)=\{u_0,w_1\}$ and $|N_W(u_i)|\le 1$ for $i=2,3,4,\ldots ,n-2$. Since $E(U',W')\le n-3$ and $|W|=n\ge 9$, there exist four vertices $w_2,w_3,w_4,w_5$ such that $N_U(w_i)\le 1$. This implies that $\overline{G}$ contains a $W_8$ formed by $u_1,u_2,u_3,u_4,$ $u_5,w_2,w_3,w_4,w_5$ with $u_1$ as the center, a contradiction. Therefore, G must contain an $S_n(3)$.

Case 2. $\varDelta (G)=n-3$. Let $u_0$ be a vertex with degree $n-3$. Let $U=N(u_0)=\{u_1,u_2,\ldots ,u_{n-3}\}$, and $W=V(G)-(U\ \cup \{u_0\})=\{w_1,w_2,\ldots ,w_{n+1}\}$.

Subcase 2.1. $E(U,W)=\emptyset$. If $\delta (G[W])\le n-4$, then $\varDelta (\overline{G}[W])\ge 4$. Let $w_1$ be a vertex with degree $\varDelta (\overline{G}[W])$ in $\overline{G}$ and $w_2,w_3,w_4,w_5\in N_{\overline{G}[W]}(w_1)$. Since $E(U,W)=\emptyset$, then the vertices $u_1,u_2,u_3,u_4,w_1,w_2,w_3,w_4,w_5$ will form a $W_8$ in $\overline{G}$ with center $w_1$, a contradiction. Therefore, $\delta (G[W])\ge n-3$. Let $w_2,w_3,\ldots w_{n-2}\in N(w_1)$, then $G[W-\{w_1\}]$ is a graph of order n with $\delta (G[W-\{w_1\}])\ge n-4$. The graph $G[W-\{w_1\}]$ cannot be $(n-4)$-regular since n is odd. Therefore, $\varDelta (G[W-\{w_1\}]) = n-3$. By Lemma 3, $G[W-\{w_1\}]$ contains an $S_n(2,1)$ and an $S_n(3)$.

Subcase 2.2. $E(U,W)\ne \emptyset$. Let $u_1w_1\in E(G)$, $U'=U-\{u_1\}$, and $W'=W-\{w_1\}$. If $\delta (G[W'])\ge n-4$, then $\varDelta (G[W'])= n-3$ because $G[W']$ cannot be $(n-4)$-regular since n is odd. But, by Lemma 3$G[W']$ contains an $S_n(2,1)$ and an $S_n(3)$.

Now, for $\delta (G[W'])\le n-5$, we will prove G contains $S_n(2,1)$. Assume to the contrary, G contains no $S_n(2,1)$. Since $E(U,W)\ne \emptyset$, let $u_1w_1\in E(G)$, $U'=U-\{u_1\}$, and $W'=W-\{w_1\}$. Since G contains no $S_n(2,1)$, then $E(U',W')=\emptyset$. Since $\delta (G[W'])\le n-5$, we have that $\varDelta (\overline{G}[W'])\ge 4$. Let $w_2$ be a vertex of degree $\delta (G[W'])$ and $w_3,w_4,w_5,w_6\in N_{\overline{G}[W']}(w_2)$, then the vertices $u_2,u_3,u_4,u_5,w_2,w_3,w_4,w_5,w_6$ will form a $W_8$ in $\overline{G}$ with $w_2$ as the center, a contradiction, and hence, G contains $S_n(2,1)$.

Next, we prove that G must contain an $S_n(3)$. Assume to the contrary that G contains no $S_n(3)$. Let $a=\max \{|N_{U'}(w_i)|:2\le i\le n+1\}$. Let $w_{n+1}$ be a vertex in $W'$ with a many neighbors in $U'$. Then, by a similar argument above, $W_1=W-\{w_{n+1}\}$ has a vertex $w_6$ with degree at most $n-5$. Let $w_2,w_3,w_4,w_5\notin N_{G[W_1]}(w_6)$. Consider the following cases.

• (a) $a \ge 2$. Let $u_2,u_3 \in N_{U'}(w_{n+1})$. Since G contains no $S_n(3)$ and $N(u_0)=U$, then there will be no edges between $\{u_0,u_1,u_2,u_3\}$ and $\{w_2,w_3,w_4,w_5,w_6\}$. Therefore, $\overline{G}$ contains $W_8$ with center vertex $w_6$ and $u_1w_2u_2w_3u_3w_4u_0w_5u_1$ as its cycle, a contradiction.

• (b) $a=1$. Let $N_{U'}(w_6)\subseteq \{u_{n-3}\}$, then $u_2,u_3,u_4,u_5\notin N_{U'}(w_6)$. Since $a=1$, let $N_{U'}(w_i)\subseteq \{u_i\}$ for $i=2,3,4,5$. Therefore, $\overline{G}$ contains a $W_8$ with center $w_6$ and $u_2w_3u_5w_4u_3w_2u_4w_5u_2$ as its cycle, a contradiction.

$\square$