The Ramsey numbers of fans versus a complete graph of order five

Yanbo Zhang, Yaojun Chen

Department of Mathematics, Nanjing University, Nanjing 210093, P.R. China

ybzhang@163.com, yaojunc@nju.edu.cn

For two given graphs F and H, the Ramsey number R(F, H) is the smallest integer N such that for any graph G of order N, either G contains F or the complement of G contains H. Let F^l denote a fan of order 2l + 1, which is l triangles sharing exactly one vertex, and Kⁿ a complete graph of order n. Surahmat et al. conjectured that R(F^l , Kn) = 2l(n − 1) + 1 for l ≥ n ≥ 5. In this paper, we show that the conjecture is true for n = 5.

Keywords: Ramsey number, fan, complete graph Mathematics Subject Classification : 05C55

1. Introduction

All graphs considered in this paper are finite simple graphs. Let G = (V (G), E(G)) be a graph with vertex set V (G) and edge set E(G). The complement of G is denoted by G. For S ⊆ V (G), G[S] denotes the subgraph induced by S in G and G − S = G[V (G) − S], NS(v) denotes the set of the neighbors of a vertex v contained in S and dS(v) = |NS(v)|. If S = V (G), we write N(v) = NG(v), N[v] = N(v) ∪ {v} and d(v) = dG(v). Let Kⁿ be a complete graph of order n and mKⁿ the union of m vertex-disjoint copies of Kn. A fan of order 2l + 1, denoted by F^l , is the join of K¹ and lK2, that is l triangles sharing exactly one vertex, where the K¹ is called the center of F^l . For notations not defined here, we follow [1]. Let F and H be two given graphs. The Ramsey number R(F, H) is the smallest integer N such that for any graph G of order N, either G contains F or G contains H. For a connected graph F of order p, Burr [2] established a general

Received: 14 October 2013, Revised: 10 March 2014, Accepted: 9 April 2014.

lower bound for R(F, H), that is, R(F, H) ≥ (p − 1)(χ(H) − 1) + s(H), if p ≥ s(H), where χ(H) is the chromatic number of H and s(H) the minimum number of vertices in some color class under all vertex colorings by χ(H) colors. For the pair F^l and Kn, noting that χ(Kn) = n and s(Kn) = 1, we have R(F^l , Kn) ≥ 2l(n − 1) + 1 by Burr's lower bound. Gupta et al. showed the equality holds for n = 3 and established the following.

Theorem 1.1 (Gupta et al. [3]). R(F^l , K3) = 4l + 1 for l ≥ 2.

Surahmat et al. proved the equality also holds for n = 4 and obtained the following.

Theorem 1.2 (Surahmat et al. [5]). R(F^l , K4) = 6l + 1 for l ≥ 3.

Maybe motivated by Theorems 1.1 and 1.2, Surahmat et al. conjectured that the equality holds in a more general case in the same paper, and posed the following.

Conjecture 1 (Surahmat et al. [5]). R(F^l , Kn) = 2l(n − 1) + 1 for l ≥ n ≥ 5.

Other results on Ramsey numbers of fans versus complete graphs can be found in the dynamic survey [4]. In this paper, we will confirm Conjecture 1 for n = 5. The main result of this paper is as below.

Theorem 1.3. R(F^l , K5) = 8l + 1 for l ≥ 5.

2. Proof of Theorem 1.3

Since 4K2^l contains no F^l and its complement contains no K5, R(F^l , K5) ≥ 8l + 1. In the following, we need only to show that R(F^l , K5) ≤ 8l + 1.

Let G be a graph of order 8l + 1 with l ≥ 5, we need to show that either G contains an F^l or G contains a K5. Suppose to the contrary that neither G contains an F^l nor G contains a K5.

Let v ∈ V (G). If d(v) ≤ 2l − 1, then G − N[v] is a graph of order at least 6l + 1. By Theorem 1.2, G−N[v] contains a K4, which implies that G contains a K5, a contradiction. If d(v) ≥ 2l+3, then a maximum matching M of G[N(v)] contains at least l edges for otherwise G[N(v)−V (M)] is a complete graph of order at least 5, which implies that G has an F^l , a contradiction. Therefore, 2l ≤ d(v) ≤ 2l + 2 for any v ∈ V (G).

Suppose that G contains a subgraph H = K2l−1. Choose v⁰ ∈ V (G) − V (H) such that dH(v0) = max{dH(v) | v ∈ V (G) − V (H)}. Obviously, G − (V (H) ∪ {v0}) is a graph of order 6l + 1. By Theorem 1.2, G − (V (H) ∪ {v0}) contains an independent set {u1, u2, u3, u4}. Since G has no K5, we have V (H) ∪ {v0} ⊆ ∪^{4 i}=1N(ui). This implies that max{dH(ui) | 1 ≤ i ≤ 4} ≥ d(2l − 1)/4e ≥ 3. By the choice of v0, we have dH(v0) ≥ 3. If dH(v0) ≥ 4, then there is some uⁱ having at least two neighbors in NH(v0) ∪ {v0}; if dH(v0) = 3, then dH(ui) ≤ dH(v0) = 3 for 1 ≤ i ≤ 4, which implies that there exists some uⁱ such that dH(ui) ≥ 2 and NH(ui)∩NH(v0) 6= ∅. In both cases, G[V (H) ∪ {v0, ui}] contains an F^l , a contradiction. Hence, G contains no K2l−1.

By Theorem 1.2, G has an independent set U = {u1, u2, u3, u4}. For 1 ≤ i ≤ 4, set Xⁱ = {v | d^U (v) = i, v ∈ V (G)}. Obviously,

\[\sum_{i=1}^{4} |X_i| = 8l - 3,\tag{1}\]

The Ramsey numbers of fans versus a complete graph of order five Yanbo Zhang and Yaojun Chen

\[\sum_{i=1}^{4} i|X_i| = \sum_{i=1}^{4} d(u_i). \tag{2}\]

Since \(\sum_{i=1}^{4} d(u_i) \le 8l + 8\), by (1) and (2), we have

\[|X_1| \ge 8l - 14 + |X_3| + 2|X_4| \ge 8l - 14. \tag{3}\]

Let \(X_{1i} = N_{X_1}(u_i)\) for \(1 \le i \le 4\). Because \(\overline{G}\) has no \(K_5\), \(G[X_{1i} \cup \{u_i\}]\) is a complete graph. Since G contains no \(K_{2l-1}\), we have \(|X_{1i} \cup \{u_i\}| \le 2l-2\), which implies that \(|X_{1i}| \le 2l-3\) for \(1 \le i \le 4\). Thus, \(|X_1| = \sum_{i=1}^4 |X_{1i}| \le 8l-12\). By (3), we have \(|X_3| + 2|X_4| \le 2\). By (1),

\[|X_2| \ge 7. \tag{4}\]

Assume without loss of generality that \(|X_{11}| \ge |X_{12}| \ge |X_{13}| \ge |X_{14}|\). Then \(|X_{11}| = |X_{12}| = 2l - 3\), \(|X_{13}| + |X_{14}| \ge 4l - 8\) and \(|X_{14}| \ge 2l - 5\). Denote by \(U_i\) both the vertex set \(X_{1i} \cup \{u_i\}\) and the graph \(G[X_{1i} \cup \{u_i\}]\) for \(1 \le i \le 4\), then \(U_1, U_2, U_3, U_4\) are pairwise vertex-disjoint complete graphs with \(|U_1| = |U_2| = 2l - 2\), \(|U_3| + |U_4| \ge 4l - 6\) and \(|U_4| \ge 2l - 4\).

Let \[Y_{ij} = N_{X_2}(u_i) \cap N_{X_2}(u_j)\] for \(1 \le i < j \le 4\).

Claim 1. If \(|U_i| = 2l - 2\) for some i with \(1 \le i \le 4\), then for any \(y \in Y_{ij}\), \(d_{U_j}(y) \ge 3\) and if \(|U_i| = |U_j| = 2l - 2\), then \(Y_{ij} = \emptyset\).

Proof. Since G contains no \(K_{2l-1}, U_i - N(y) \neq \emptyset\). In this case, \(G[U_i \cup U_j - N(y)]\) is a complete graph for otherwise any two nonadjacent vertices in \(G[U_i \cup U_j - N(y)]\) together with \(U \cup \{y\} - \{u_i, u_j\}\) form a \(K_5\) in \(\overline{G}\), a contradiction. Since G has no \(F_l\) and both \(U_i\) and \(U_j\) are complete graphs, we have \(d_{U_j}(u) \leq 3\) for any \(u \in U_i\), which implies that \(|U_j - N(y)| \leq 3\). Noting that \(|U_j| \geq 2l - 4\) and \(l \geq 5\), we have \(d_{U_j}(y) \geq |U_j| - |U_j - N(y)| \geq (2l - 4) - 3 \geq 3\).

If \(|U_i| = |U_j| = 2l - 2\) and \(Y_{ij} \neq \emptyset\), then for any \(y \in Y_{ij}\), \(d_{U_i}(y) + d_{U_j}(y) \leq 2l\) since otherwise G[N[y]] contains an \(F_l\) with y as center, a contradiction. Thus we have \(|U_i \cup U_j - N(y)| \geq |U_i| + |U_j| - 2l \geq 6\) since \(l \geq 5\). By the arguments in the first part, we have \(|U_i - N(y)| = |U_j - N(y)| = 3\). Thus, \(G[U_i \cup (U_j - N(y))]\) contains an \(F_l\) with u as center for any \(u \in U_i - N(y)\), a contradiction. Hence \(Y_{ij} = \emptyset\).

If \(|U_4|=2l-2\), then by Claim 1, \(X_2=\cup_{1\leq i< j\leq 4}Y_{ij}=\emptyset\) which contradicts (4). Hence we have \(2l-4\leq |U_4|\leq 2l-3\).

Assume \(|U_3|=2l-2\). By Claim 1, we have \(X_2=\cup_{1\leq i< j\leq 4}Y_{ij}=Y_{14}\cup Y_{24}\cup Y_{34}\), that is, \(X_2\subseteq N(u_4)\). If \(|U_4|=2l-3\), then since \(\sum_{i=1}^4 d(u_i)\leq 8l+8\), by (1), (2) and (3), either \(|X_2|=10\), \(|X_3|=|X_4|=0\) and \(\sum_{i=1}^4 d(u_i)=8l+7\) or \(|X_2|=9\), \(|X_3|=1\), \(|X_4|=0\) and \(\sum_{i=1}^4 d(u_i)=8l+8\). If \(|U_4|=2l-4\), then for the same reason, we have \(|X_2|=11\), \(|X_3|=|X_4|=0\) and \(\sum_{i=1}^4 d(u_i)=8l+8\). Thus we have \(|X_2|\geq 9\) in both cases, which implies that \(d(u_4)\geq |X_{14}|+|X_2|\geq 2l-5+9=2l+4\), a contradiction. Therefore, \(|U_3|\leq 2l-3\).

Since \(|U_3| + |U_4| \ge 4l - 6\) and \(|U_4| \le 2l - 3\), we are now left to consider the case when \(|U_3| = |U_4| = 2l - 3\). Since \(\sum_{i=1}^4 d(u_i) \le 8l + 8\), by (1), (2) and (3), we have \(|X_2| = 11\), \(|X_3| = |X_4| = 0\) and \(\sum_{i=1}^4 d(u_i) = 8l + 8\), which implies \(d_{X_2}(u_4) = 6\). Let \(N_{X_2}(u_4) = \{y_i \mid 1 \le i \le 6\}\). Since \(\overline{G}\) contains no \(K_5\), \(G[N_{X_2}(u_4)]\) contains at least one edge, say \(y_1y_2 \in E(G)\). Since G has no \(F_l\),

\(G[\{y_3,y_4,y_5,y_6\}]\) contains no edge. Because \(\overline{G}\) has no \(K_5\), we have \(|\{y_3,y_4,y_5,y_6\}\cap (N(u_1)\cup N(u_2))|\geq 2\). Assume that \(\{y_3,y_4\}\subseteq N(u_1)\cup N(u_2)\). By Claim \(1,d_{U_4}(y_3)\geq 3\) and \(d_{U_4}(y_4)\geq 3\), which implies that \(d_{X_{14}}(y_3)\geq 2\) and \(d_{X_{14}}(y_4)\geq 2\). In this case, there exist \(u',u''\in X_{14}\) such that \(u'y_3,u''y_4\in E(G)\), which implies that \(G[U_4\cup\{y_1,y_2,y_3,y_4\}]\) contains an \(F_l\) with \(u_4\) as center, a contradiction.

The proof of Theorem 1.3 is completed.

Acknowledgement

This research was supported by NSFC under grant numbers 11071115, 11371193 and 11101207, and in part by the Priority Academic Program Development of Jiangsu Higher Education Institutions.

References

• [1] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, 2008.
• [2] S.A. Burr, Ramsey numbers involving graphs with long suspended paths, Journal of London Mathematical Society 24 (1981), 405–413.
• [3] S.K. Gupta, L. Gupta and A. Sudan, On Ramsey numbers for fan-fan graphs, Journal of Combinatorics, Information & System Sciences 22 (1997), 85–93.
• [4] S.P. Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics, (2011), DS1.13.
• [5] Surahmat, E.T. Baskoro and H.J. Broersma, The Ramsey numbers of fans versus \(K_4\), Bulletin of the Institute of Combinatorics and its Applications 43 (2005), 96–102.