Hilda Assiyatun, Budi Rahadjeng^1∗ , Edy Tri Baskoro

Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia

hilda@math.itb.ac.id, budi.rahadjeng@students.itb.ac.id, ebaskoro@math.itb.ac.id

Let F, G, and H be simple graphs. The notation F → (G, H) means that if all the edges of F are arbitrarily colored by red or blue, then there always exists either a red subgraph G or a blue subgraph H. The size Ramsey number of graph G and H, denoted by rˆ(G, H) is the smallest integer k such that there is a graph F with k edges satisfying F → (G, H). In this research, we will study a modified size Ramsey number, namely the connected size Ramsey number. In this case, we only consider connected graphs F satisfying the above properties. This connected size Ramsey number of G and H is denoted by rˆc(G, H). We will derive an upper bound of rˆc(nK2, H), n ≥ 2 where H is 2P^m or 2K1,t, and find the exact values of rˆc(nK2, H), for some fixed n.

Keywords: connected size Ramsey number, disconnected graph, matching

Mathematics Subject Classification : 05D10, 05C55

DOI: 10.5614/ejgta.2019.7.1.9

1. Introduction

All graphs in this paper are finite, undirected, and simple. Let F, G, and H be graphs. The number of vertices and edges of graph F will be denoted by |V (F)| and |E(F)|, respectively. The notation F → (G, H) means that in any red-blue coloring of the edges of F there exists a red

Received: 19 February 2018, Revised: 19 August 2018, Accepted: 5 January 2019.

¹ Permanent Affiliation: Universitas Negeri Surabaya, Indonesia.

^*Corresponding author.

copy of G or a blue copy of H in F. We denote F 9 (G, H) to mean that there is some red-blue coloring of the edges of F such that F contains neither a red G nor a blue H. This coloring is called a (G, H)-coloring of F.

The size Ramsey number for a pair of graphs G and H, denoted by rˆ(G, H), is the smallest integer k such that there is a graph F with k edges satisfying F −→ (G, H). The concept of size Ramsey number of a graph was introduced by Erdos et al. in [2]. A survey of results about the size ˝ Ramsey number for a pair of graphs can be seen in [4]. There are only a few results concerning the size Ramsey number for a pair of graphs, namely the size Ramsey numbers involving a complete graph, a star, a cycle or a path. Further results have also been obtained, for instance the size Ramsey number for some regular graphs [5] and the size Ramsey of a directed path [6].

A matching, denoted by nK2, n ≥ 2, is the graph consisting of 2n vertices and n independent edges. In 1978, Burr et.al [1] determined the size Ramsey number for a pair of graphs involving matching, rˆ(nK1,s, mK1,t) = (n+m−1)(s+t−1), for positive integers s, t, m, and n. The smallest graphs F satisfying this size Ramsey number are (m+n−1)K1,(s+t−1) and lK3∪(m+n−l−1)K1,³ for s = t = 2, 1 ≤ l ≤ m + n − 1, namely (m + n − 1)K1,(s+t−1) → (nK1,s, mK1,t) or lK3∪(m+n−l−1)K1,³ → (nK1,2, mK1,2). These two graphs are disconnected. The other result on the size Ramsey number involving matching was obtained by Erdos and Faudree [3]. They ˝ showed that rˆ(2K2, Pm) = m + 1, where the smallest graph satisfying the size Ramsey number is a Cm+1, namely Cm+1 → (2K2, Pm). Note that in this case, we have a connected smallest graph F satisfying F → (G, H).

Therefore, in general we have either connected or disconnected graph F with smallest size and satisfying F → (G, H), for given G and H. In this paper, we are interested in finding a connected graph F with minimum size and satisfying F → (G, H). The smallest size of a connected graph F so that F → (G, H) is called the connected size Ramsey number and denoted by rˆc(G, H).

Some results on the connected size Ramsey number for a pairs of graphs were established. Rahadjeng et al. [8] determined the connected size Ramsey number for the pairs (2K2, K1,m) and (3K2, K1,m). Then, in [7], they showed that rˆc(nK2, K1,3) = 4n − 1, for n ≥ 2.

In this paper, we will determine an upper bound of rˆc(nK2, H), n ≥ 2 where H is isomorphic to 2P^m or 2K1,t. We also determine the exact values of rˆc(nK2, H) for some fixed n.

2. Main Results

In this section, we present the following results.

Theorem 2.1. For \[m \geq 2\], \(\hat{r}_c(2K_2, 2P_m) = 2m + 1\).

Proof. First, we will show that rˆc(2K2, 2Pm) ≤ 2m + 1. To do this, we will define the connected graph F having 2m + 1 edges satisfying F → (2K2, 2Pm). Consider the graph F = C2m+1. Let µ be any red-blue coloring of F such that there is no red 2K2. Then, there is no red edge in F or a red subgraph in F is isomorphic to either P² or P3. Let us consider a subgraph F ⁰ = F − E(Pi) with i = 2 or 3. Certainly, F 0 is isomorphic to either a path P2m+1 or P2m. Since the necessary condition of the path containing 2P^m is having at least 2m vertices, then obviously F 0 contains 2Pm. Hence, F → (2K2, 2Pm).

Now, we will show that \(\hat{r}_c(2K_2, 2P_m) \ge 2m + 1\). Let G be a connected graph with \(|E(G)| \le 2m\). We will show that \(G \nrightarrow (2K_2, 2P_m)\). We are going to prove it by using the number of vertices of G.

First, we assume that |V(G)|=2m+1. In this case, G is a tree. Let \(P=v_1,v_2,...,v_k\) be the longest path in G, with \(k \leq 2m+1\). Choose one vertex of V(P), say \(v_i\), so that \(G-v_i\) contains no \(2P_m\). Color all edges incident with \(v_i\) by red and all edges in \(G-v_i\) by blue. By this coloring, there is a \((2K_2, 2P_m)\)-coloring on F. Thus, \(G \rightarrow (2K_2, 2P_m)\).

Next, suppose that \(|V(G)| \leq 2m\). Let us consider a complete graph \(K_{2m}\). For every \(v \in V(K_{2m})\), \(K_{2m} - v \not\supseteq 2P_m\). Since all graphs of order 2m and size 2m are proper subgraphs of \(K_{2m}\), then we can color all edges of G with red-blue so that there exists a \((2K_2, 2P_m)\)-coloring in G. Thus, \(G \to (2K_2, 2P_m)\).

Theorem 2.2. \[\hat{r}_c(nK_2, 2P_3) \leq \begin{cases} 3n+1, & \textit{for } n=3,4,5,6,7, \\ 5(\frac{n}{2})+4, & \textit{for even } n, n \geq 8, \\ 5\left(\frac{n+1}{2}\right)+2, & \textit{for odd } n, n \geq 9. \end{cases}\]

Proof. We will find a connected graph F such that \(F \to (nK_2, 2P_3)\). First, we will prove for the case of \(n \in [3, 7]\). Let us consider the graph \(F = C_{3n+1}\).

Let \(\mu\) be any red-blue coloring of F that maximizes the number of red edges and contains no red \(nK_2\). The red subgraph of F contains at most 2(n-1) edges. The remaining edges, which are blue, are at least 3n+1-2(n-1)=n+3. This blue subgraph consists of at most n-1 disjoint paths. By the pigeon-hole principle, there are at least two disjoint paths of length 2. Thus F contains blue \(2P_3\). Hence \(F \to (nK_2, 2P_3)\).

For the case of even n and \(n \geq 8\), we consider the graph in Figure 1. The graph G contains \((\frac{n}{2}+1)\) disjoint cycles of length 4 and \(\frac{n}{2}\) disjoint edges. Thus, the number of edges of G is \(4(\frac{n}{2}+1)+\frac{n}{2}=5(\frac{n}{2})+4\). Let \(\mu\) be any red-blue coloring of G such that there is no red \(nK_2\).

Figure 1. The graph \(G \to (nK_2, 2P_3)\), for even n.

Observe that for each 4-cycle in G, we find at most two red \(K_2\). Since G contains no red \(nK_2\), we have at most \((\frac{n}{2}-1)\) 4-cycles containing two red \(K_2\) and one 4-cycle containing at most one red \(K_2\). As a consequence, we have at least one 4-cycle whose all edges are blue and one 4-cycle which at least 2 consecutive edges are blue. Since those two 4-cycles are separated by at least an edge, G contains a blue \(2P_3\). Thus, \(G \to (nK_2, 2P_3)\).

For the case of odd \(n, n \geq 9\), let consider the graph in Figure 2. The graph F contains \(\left(\frac{n+1}{2}\right)\) disjoint cycles of length 4, \(\left(\left(\frac{n+1}{2}\right)-1\right)\) disjoint edges and one star \(K_{1,3}\). Thus, the number of edges of F is \(4\left(\frac{n+1}{2}\right)+\left(\left(\frac{n+1}{2}\right)-1\right)+3=5\left(\frac{n+1}{2}\right)+2\).

Figure 2. The graph \(F \to (nK_2, 2P_3)\), for odd n.

Let \(\mu\) be any red-blue coloring of F such that there is no red \(nK_2\). By a similar argument as in the case for even n, there are at most \((\frac{n+1}{2}-1)\) 4-cycles containing red \(2K_2\). As a consequence, we have at least one 4-cycle which all edges are blue and a blue star \(K_{1,3}\). Thus, \(G \to (nK_2, 2P_3)\). \(\square\)

Theorem 2.3. \(\hat{r}_c(3K_2, 2P_3) = 10.\)

Proof. According Theorem 2.2, \(\hat{r}_c(3K_2, 2P_3) \leq 10\). Now, we will prove that \(\hat{r}_c(3K_2, 2P_3) \geq 10\). Suppose that F is a connected graph with \(|E(F)| \leq 9\). We will show that \(F \nrightarrow (3K_2, 2P_3)\). Decompose F into two connected subgraph \(F_1\) and \(F_2\) with \(|E(F_1)| \leq 3\) and \(|E(F_2)| \leq 6\). Consider that the subgraph \(F_1\) is isomorphic to a star \(K_{1,3}\) or a cycle \(C_3\) or a path \(P_4\). If \(F_1\) is a star \(K_{1,3}\) or a cycle \(C_3\), then color all edges in \(F_1\) with red. According Theorem 2.1 \(\hat{r}_c(2K_2, 2P_3) = 7\), then there is a \((2K_2, 2P_3)\) — coloring in \(F_2\). Therefore, F contains at most two red \(K_2\) and no blue \(2P_3\). So, \(F \nrightarrow (3K_2, 2P_3)\).

Now, suppose that \(F_1\) is a path \(P_4\). We claim there are at most 2 common vertices of \(F_1\) and \(F_2\). Suppose there are 3 common vertices of \(F_2\) and \(F_1\). Consider the following graph. Let \(v_i^1\) and \(v_i^2\) be vertices of \(F_1\) and \(F_2\), respectively. Since \(F_2\) is connected, there is a vertex \(v_k^2\) of \(F_2\) adjacent

to \(v_j^2\), j=5 or 6 or 7. Therefore, if we remove the vertex \(v=v_2^1\), the graph F-v is connected. Hence, this is the same as the previous case, namely when \(F_1\) is a star \(K_{1,3}\). So, there are at most two common vertices of \(F_1\) and \(F_2\), as claimed.

By Theorem 2.1, there is a \((2K_2, 2P_3)\) – coloring in \(F_2\). Observe that, if there are at least two blue paths in \(F_2\), the longest one is \(P_4\). Therefore, we color two consecutive edges in \(F_1\) with red and the other edge with blue so that the blue edge of \(F_1\) is adjacent to the longest blue path in \(F_2\) (if any). Otherwise, the blue edge of \(F_1\) is adjacent to the red edges of \(F_2\). In this coloring, F contains at most two red \(K_2\) and no blue \(2P_3\). So, \(F \rightarrow (3K_2, 2P_3)\). Thus, \(\hat{r}_c(3K_2, 2P_3) \geq 10\). Combining the two inequalities, we have \(\hat{r}_c(3K_2, 2P_3) = 10\).

Theorem 2.4. rˆc(nK2, 2P3) = 3n + 1, for n = 3, 4, 5, 6, 7.

Proof. By Theorem 2.2, we obtain rˆc(nK2, 2P3) ≤ 3n + 1. Now, we will prove rˆc(nK2, 2P3) ≥ 3n + 1. Suppose that F is a connected graph with |E(F)| ≤ 3n. We will show that F 9 (nK2, 2P3). We proceed by induction on n. The assertion is true for n = 3. Furthermore, we may assume that rˆc(kK2, 2P3) ≥ 3k + 1, for all n ≤ k ≤ 6.

Let F ⁰ be a connected graph with |E(F 0 )| ≤ 3(k + 1). Decompose F 0 into two connected subgraphs F¹ and F² with |E(F1)| ≤ 3 and |E(F2)| ≤ 3k. Consider that the subgraph F¹ isomorphic to a star K1,³ or a cycle C³ or a path P4. If F¹ is a star K1,³ or a cycle C3, then color all edges in F¹ with red. Next, by the induction hypothesis, there is a (kK2, 2P3)− coloring in F2. By combining the coloring in F¹ and F2, there exists at most k red K² and no blue 2P³ in F 0 . So, F 9 ((k + 1)K2, 2P3).

Now, assume that F¹ is a path P4. There are at most two common vertices of F¹ and F2, as in the previous theorem, namely x and y. Consider (kK2, 2P3)− coloring in F2, that maximizes the number of red edges and minimizes the length of blue paths. If at most one of x and y is adjacent with a blue edge in F2, then we color two consecutive edges in F¹ with red and the other edge with blue so that the blue edge in F² is adjacent with red edges in F1. If both x and y are adjacent with blue edges in F2, we claim that the longest blue path in F² is P4. Suppose the longest blue path in F² is P5. Let F 0 ² = F² − P5. Observe that |F 0 2 | ≤ 3k − 4. We can view the coloring in F 0 2 as a chain of alternating blue and red subgraphs, starting with a blue subgraph and ending with a red subgraph. As the number of red edges is maximized, there are at least 2(k − 1) red edges in F 0 2 . Thus, the number of edges in F 0 2 is at least (k − 1) + 2(k − 1) = 3k − 3, a contradiction. So, the longest blue path in F² is P4, as claimed. Color two consecutive edges in F¹ with red and the other edge with blue so that the blue edge in F¹ is adjacent with the longest blue path of F² (if any). In this coloring, F 0 contains at most k red K² and no blue 2P3. So, F ⁰ 9 ((k + 1)K2, 2P3). Thus, rˆc((k + 1)K2, 2P3) ≥ 3(k + 1) + 1.

Combining the two inequalities, we conclude that rˆc(nK2, 2P3) = 3n + 1, for 3 ≤ n ≤ 7.

Theorem 2.5. rˆc(8K2, 2P3) = 24.

Proof. By Theorem 2.2, we obtain rˆc(8K2, 2P3) ≤ 24. Now, we will prove rˆc(8K2, 2P3) ≥ 24. Suppose that F is a connected graph with |E(F)| ≤ 23. We will show that F 9 (8K2, 2P3). Decompose F into two connected subgraphs F¹ and F² with |E(F1)| ≤ 2 and |E(F2)| ≤ 21. Color all edges in F¹ with red. According to Theorem 2.4, rˆc(7K2, 2P3) = 22. Thus there is a (7K2, 2P3)− coloring in F2. By combining the coloring in F¹ and F2, there are at most 7 red K² and no blue 2P³ in F. So, F 9 (8K2, 2P3). Hence, rˆc(8K2, 2P3) ≥ 24. Combining the two inequalities, we may conclude that rˆc(8K2, 2P3) = 24.

Theorem 2.6. For m ≥ 3, n ≥ 3, rˆc(nK2, 2K1,m) = mn + m + n.

Proof. First, we will show that rˆc(nK2, 2K1,m) ≤ mn+m+n. Let G be a graph obtained from one cycle C2n+1 and (n+1) stars K1,m−¹ by identifying the vertex of degree m−1 of K1,m−¹ to the vertices of C2n+1, where two vertices of C2n+1 are adjacent and the other n − 1 vertices have distance two from the other, as depicted in Figure 3. The graph G has 2n+1+(m−1)(n+1) = mn+m+n edges.

Figure 3. The graph G satisfy G → (nK2, 2K1,m).

Let µ be any red-blue coloring of G such that there is no red nK2. Then, all edges of G are colored by blue or the red subgraph G^∗ of G forms a path of length at most 2(n − 1) or a subgraph containing at most (n − 1) stars K1,i, i ≤ m + 1. Let G⁰ be a subgraph of G without edges of the red subgraph G^∗ . This subgraph G⁰ forms a path of length at least 3 having at least two vertices of degree ≥ m or a disconnected graph containing 2 disjoint K1,m. Hence, G contains a blue 2K1,m. So, G → (nK2, 2K1,m). Thus, rˆc(nK2, 2K1,m) ≤ mn + m + n.

Now, we will show that rˆc(nK2, 2K1,m) ≥ mn + m + n. Let G be a connected graph with |E(G)| ≤ mn + m + n − 1. We will show that G 9 (nK2, 2K1,m). Consider the following cases.

Case 1. ∆(G) < m.

Color all edges in G with blue. By this coloring, there is a (nK2, 2K1,m)− coloring in G.

Case 2. ∆(G) ≥ m.

Let A be the set of vertices of degree at least m in G. If |A| ≤ n − 1, then color all edges incident with all vertices in A by red and the other edges by blue. By this coloring, there is a (nK2, 2K1,m)− coloring in G.

Next, we assume that |A| ≥ n. Since |E(G)| ≤ mn + m + n − 1, there are at most n disjoint K1,m in G, otherwise G has at least mn + m + n edges, a contradiction.

Suppose G contains at most n disjoint stars K1,m.

Let C be the set of centers of n disjoint K1,m. Observe that, the remaining edges of G are at least m. We consider these remaining edges. If these edges induce no K1,m, then we choose n − 1 vertices of C and then color all edges incident with these vertices by red. Next, we color the remaining edges of G with blue. By this coloring, we obtain a (nK2, 2K1,m)-coloring in G.

Now, suppose these edges induce a K1,m with center u. Since G is connected, then at least one vertex of the K1,m is adjacent to a vertex of C, say vⁱ⁰ . Therefore, u and vⁱ⁰ have distance at most 2. If u is adjacent to vⁱ⁰ , we color all edges incident with u by red. Next, choose at most (n − 2) vertices of C that are different with vⁱ⁰ (if any) and color all edges incident with these vertices by red. By coloring all the remaining edges of G by blue, we obtain a (nK2, 2K1,m)-coloring in G. Suppose u is not adjacent to vⁱ⁰ . In this case, we choose a path P³ connecting u and vⁱ⁰ and color the P³ with red. Furthermore, similar as in the previous case, choose at most (n − 2) vertices of C that are different with vⁱ⁰ (if any) and color all edges incident with these vertices by red. By giving the blue color to the remaining edges of G, we obtain a (nK2, 2K1,m)− coloring in G. Hence, in all cases, we have that G 9 (nK2, 2K1,m).

Acknowledgement

This research has been partially supported by Research Grant: "Penelitian Dasar Unggulan Perguruan Tinggi (PDUPT)" and "Penelitian Disertasi Doktor", the Ministry of Research, Technology and Higher Education, Indonesia.

References

• [1] S.A. Burr, P. Erdos, R.J. Faudree, C.C. Rousseau, R.H. Schelp, Ramsey minimal graphs for ˝ multiple copies, Nederl. Akad. wetensch, Proc. Ser. A81 (1978), 187–195.
• [2] P. Erdos, R. J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, ˝ Period. Math. Hungar. 9 (1-2) (1978), 145–161.
• [3] P. Erdos, R.J Faudree, Size Ramsey numbers involving matching, ˝ Finite and infinite sets, Colloq. Math. Soc. Janos Bolyai ´ 37 (1981), 247–264.
• [4] R.J. Faudree, R.H. Schelp, A survey of results on the size Ramsey number, in Paul Erdos and ˝ his mathematics II (Budapest, 1999), Bolyai Soc. Math. Stud. 11 (2002), 291–309.
• [5] H. Bielak, Note size Ramsey number for some regular graphs, Discrete Math. 309 (2012), 6446–6449.
• [6] I. Ben-Eliezer, M. Krivelevich, B. Sudakov, The size Ramsey of a directed path, J. Combin. Theory 102 (2012), 743–755.
• [7] B. Rahadjeng, E.T. Baskoro, H. Assiyatun, Connected size Ramsey numbers for matchings vs small stars or cycles, Proc. Indian Acad. Sci. Math. Sci. 127 (5) (2017), 787–792.
• [8] B. Rahadjeng, E.T. Baskoro, H. Assiyatun, Connected size Ramsey numbers of matchings and stars, AIP Conf. Proc., 1707, 020015 (2016); doi :10.1063/1.4940816.