1 Introduction
Let G be a graph with the vertex set, edge set, order, and size are V(G), E(G), v(G), and e(G), respectively. We denote the degree of a vertex \(v \in V(G)\) by d(v) and the minimum (resp. maximum) degree of vertices in G by \(\delta(G)\) (resp. \(\Delta(G)\)). Let \(H \subseteq G\). A graph G - H is obtained from G by deleting all edges in G. Further terminology related to graphs can be found in [1].
The size Ramsey number of graphs G and H, \(\hat{r}(G,H)\), is the smallest size of graph F such that for any red-blue coloring of all edges of F we have a subgraph G in red color or a subgraph H in blue color. If the order of F in the size Ramsey number must be equal to r(G,H), then we call it the restricted size Ramsey number, \(r^*(G,H)\). The Ramsey number of graphs G and H, r(G,H), is the minimum order F of F0 such that any red-blue coloring of its edges contains a subgraph G1 in red color or a subgraph F1 in blue color. Furthermore, we say F2 arrowing graphs F3 and F4, denoted by F5 or F6, F7, if any red-blue coloring of
Received January 30<sup>th</sup>, 2018, 1<sup>st</sup> revision November 14<sup>th</sup>, 2019, 2<sup>nd</sup> Revision December 22<sup>nd</sup>, 2019, Accepted for publication January 16<sup>th</sup>, 2020
Copyright © 2020 Published by ITB Institute for Research and Community Services, ISSN: 2337-5760, the edges of ܨ contains a subgraph ܩ in red color or a subgraph ܪ in blue color. In addition, a red-blue coloring of the edges of ܨ is called (ܩ, ܪ(-݃݀ if under this coloring, ܨ does not contain ܩ in red color and ܪ in blue color. The notation ܨ) ↛ ܩ, ܪ (means that there exists a (ܩ, ܪ(-good coloring in ܨ.
The concept of the size Ramsey number was introduced by Erdös, et al. [2] in 1978, who also gave some results for this problem. Long before this introduction, the concept of the Ramsey number had already been established in graph theory. The restricted size Ramsey number is a direct consequence of the concept of the size Ramsey and Ramsey number in graphs. Some results on the size Ramsey number and the restricted size Ramsey number of graphs can be found in [3-6].
To find the exact values of the (restricted) size Ramsey number for a pair of graphs is challenging, even for a pair of small graphs. In 1983, Harary and Miller [7] initiated the investigation on the (restricted) size Ramsey number for a pair of small graphs. They obtained some exact values for a pair of graphs with order not more than four. However, since the proof is long and needs a tedious amount of work, they omitted the proof of some of their results. Faudree and Sheehan [8] continued the investigation and compiled the complete values for the (restricted) size Ramsey number for any pair of graphs with order not more than four. They also did not give any proof of their results. Lortz and Mengenser (1998) in [9] continued the investigation and derived the size and the restricted size Ramsey numbers for all pairs of small forests with order not more than five.
For the same reason as given by Faudree and Sheehan [8], they also did not provide proof of their results. Recently, in [6] we gave the restricted size Ramsey number for pairs of a path ܲଷ and any connected graph of order five. We presented the complete proof for this case. To carry on the research on the restricted size Ramsey number involving small graphs, we investigated the restricted size Ramsey number for pairs of a matching with two edges, 2ܭଶ, and graph with no isolates of order five.
2 Preliminaries
The list of all graphs of order five that do not have isolated vertices is given in Figure 1. In 1972, Chvátal and Harary [10] gave the Ramsey number for 2ܭଶ and any graph with no isolates, as stated in Theorem 1. This theorem provides the order of graph ܨ such that ܨ) → 2ܭଶ, ܪ(, in finding ݎ)∗2ܭଶ, ܪ(.
Figure 1 List of graphs with no isolates with order 5.
Theorem 1 [10] For any graph H with no isolates,
\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]
Some exact values of \(r^*(2K_2, H)\) when H is a connected graph of order five are already known. From the results of Lortz and Mengenser [9] we have \(r^*(2K_2, H_1) = 6\), \(r^*(2K_2, H_2) = 8\), \(r^*(2K_2, H_3) = 12\), and \(r^*(2K_2, H_4) = 6\). Furthermore, from our previous results in [11] we have \(r^*(2K_2, H_7) = 12\), \(r^*(2K_2, H_{14}) = 13\), \(r^*(2K_2, H_{18}) = 15\), \(r^*(2K_2, H_{19}) = 13\), \(r^*(2K_2, H_{20}) = 14\), \(r^*(2K_2, H_{21}) = 15\), \(r^*(2K_2, H_{22}) = 15\) and \(r^*(2K_2, H_{23}) = 21\). For the remaining graph \(H_i\), we will derive the exact values for \(r^*(2K_2, H_i)\). To prove some of our results, we use Theorem 2.
Theorem 2 [11] For n > 3.
\[r^*(2K_2, K_n) = \{(n+22), n \ge 4, (n2) - 1, n = 3\}\] where (n r) is a combination of n objects taken r at a time.
Obviously, the following monotonicity property can be derived from the definition of the (restricted) size Ramsey number. If \(G' \subseteq G\) and \(H' \subseteq H\), then
\[\hat{r}(G', H') \le \hat{r}(G, H) \tag{1}\] and
\[r^*(G',H') \le r^*(G,H) \tag{2}\]
Note that Chvátal and Harary [10] gave this kind of monotonicity property for the Ramsey number of a pair of graphs.
3 Main Results
In this section, we present \(r^*(2K_2, H_i)\) for which the values are not yet known. Since \(r^*(2K_2, K_5) = 21\) is already known, our goal is to find \(r^*(2K_2, H_i)\) for all
ܪ in Figure 1, except ܪଶଷ or ܭହ. Using Theorem 1 we obtain ݎ)2ܭଶ, ܪ=(6 for every ܪ in our consideration. For any pair of graphs ܩ and ܪ, it is known have we ,bound this Using . )2) ܪ ,ܩ)ݎ) ≥ (ܪ ,ܩ)∗ݎ≥−1 (ܪ)݁ + (ܩ)݁ that ݁(ܪ (+1≥ݎ)∗2ܭଶ, ܪ ≥ (15 for all ܪ in our consideration. We will give ݎ)∗2ܭଶ, ܪ (for ܪ a graph that contains a ܥଷ in Theorems 3 and 4; ܪ a graph that contains a ܥସ in Theorems 5, 7, and 6; ܪ a graph that contains a ܥହ in Theorems 8, 9, and 10; and the remaining in Theorem 11.
Lemmas 1 and 2 give the properties of graph ܨ such that ܨ) → 2ܭଶ, ܪ (for any graph ܪ without isolates. Lemma 1 is a generalization of the lemma given in [12], which they gave for ܪ=ܭଵ,. Actually, the lemma holds for any graph ܪ and the proof is similar to the proof in [12]. Lemmas 3 and 4 give the properties of ܨ such that ܨ) → 2ܭଶ, ܪ (when graph ܪ contains cycles. We will use all these lemmas in proving our theorems.
Lemma 1. Let ܪ be a graph. ܨ) → 2ܭଶ, ܪ (holds if and only if the following conditions are satisfied:
- and) ܨ)ܸ ∋ ݒ every for ݒ−ܨ⊇ܪ 1.
- .ܨ in ଷܥ every for ଷܥ−ܨ⊇ܪ 2.
Lemma 2. Let ܪ be a graph with no isolates. If ܨ) → 2ܭଶ, ܪ (and ݒ)ܨ= ( 2. ≤ (ܨ)ߜ then ,)ܪ ,ଶܭ2)ݎ 2 Theorem then ,)ܪ ,ଶܭ2)ݎ = (ܨ)ݒ and ,)ܪ ,ଶܭ2) → ܨ ,ܭ≅ܪ If .Proof implies ߜ)ܨ ≤ (2. If ܪ≇ܭ, then using Theorem 1 we obtain ݒ)ܨ = (݊ + 1. 1. ≥ (ܨ)ߜ and 1, + ݊) = ܨ)ݒ ,(ܪ ,ଶܭ2) → ܨ that contrary the to Suppose Assume ݑ is a vertex with ݀(ݑ = (1 and ݒ is a neighbor of ݑ. The graph ܨ−ݒ consists of a component with order ݊−1 and an isolate. Obviously, ܪ⊇/ܨ−ݒ and Lemma 2 implies ܨ) ↛ 2ܭଶ, ܪ(. We have a contradiction.
Lemma 3. For ݊≥4, let ܪ be a graph with ݒ)ܪ = (݊ and ܪ contains a cycle of length ݐ, ܥ௧, for 3≤ݐ≥݊. If ܨ) → 2ܭଶ, ܪ(, then ܨ contains at least two ܥ௧ which do not share a vertex and are not incident to a ܥଷ.
Proof. For ݊≥4, let ܪ be a graph with ݒ)ܪ = (݊ and ܥ௧ ⊆ ܪ for 3≤ݐ≥݊. Suppose to the contrary that ܨ) → 2ܭଶ, ܪ (and all ܥ௧ for 3≤ݐ≥݊ in ܨ share a vertex or are incident to a ܥଷ. If all ܥ௧ in ܨ share a vertex ݒ, then ܪ⊇/ܨ−ݒ and if all ܥ௧ in ܨ are incident to a ܥଷ, then ܪ⊇/ܨ−ܥଷ. Lemma 1 implies ܨ) ↛ 2ܭଶ, ܪ(. We have a contradiction.
In Figure 2(a) we give an example of a graph that contains more than one ܥଷ but all share a vertex ݒ. By removing ݒ, it means that by coloring all edges incident to v red (edges in dotted line), \(C_3 \nsubseteq F - v\). In Figure 2(b) we give an example of a graph that contains more than one \(C_3\) but all are incident to a \(C_3\) (let's call it \(C_3\)). By removing \(C_3\), it means that by coloring all edges belonging to \(C_3\) as red (edges in dotted line), \(C_3 \nsubseteq F - C_3\).
Figure 2 Examples for Lemma 3.
Lemma 4. For \(n \ge 4\), let H be a graph with v(H) = n and H contains a cycle with length n - 1. If \(F \to (2K_2, H)\) and \(v(F) = r(2K_2, H)\), then \(\delta(F) \ge 3\).
Proof. For \(n \geq 4\), let H be a graph with v(H) = n and \(C_{n-1} \subseteq H\). If \(H \cong K_n\), \(F \to (2K_2, H)\), and \(v(F) = r(2K_2, H)\), then Theorem 2 implies \(\delta(F) \geq 3\). If \(H \ncong K_n\), then using Theorem 1 we obtain v(F) = n + 1. Suppose to the contrary that \(F \to (2K_2, H)\), v(F) = n + 1, and \(\delta(F) \leq 2\). Lemma 2 implies \(\delta(F) = 2\). Suppose u is a vertex with degree 2 and v is a neighbor of u. The degree of u in F - v is 1. Since v(F) = n + 1, it is clear that \(C_{n-1} \nsubseteq F - v\). Hence, Lemma 1 implies \(F \to (2K_2, H)\). We have a contradiction.
Theorem 3. \(r^*(2K_2, H_5) = r^*(2K_2, H_8) = 10.\)
Proof. We know that \(r(2K_2, H_5) = r(2K_2, H_8) = 6\). Note that \(C_3 \subseteq H_5 \subseteq H_8\). To show the upper bound, consider \(F = K_6 - (C_4 \cup K_2)\). All vertices in F have degree either 3 or 4. The graph F - v with d(v) = 3 is a wheel without a spoke and F - v with d(v) = 4 is a graph containing two triangles that share a vertex. It is clear that \(H_8 \subseteq F - v\) for both kind of vertices. Furthermore, all \(C_3\) in F are isomorphic, involving two vertices with degree 3 and a vertex with degree 4. It is easy to verify that \(H_8 \subseteq F - C_3\) for every \(C_3\). Hence, Lemma 1 implies \(F \to (2K_2, H_8)\), so \(r^*(2K_2, H_8) \le 10\). Since \(H_5 \subseteq H_8\), by (2) we obtain \(r^*(2K_2, H_5) \le 10\).
Figure 3 Graphs F that satisfy the conditions for the lower bound of Theorem 3.
To show the lower bound, we must consider all graphs F with v(F) = 6 and e(F) = 9. According to Lemma 2 and 3, \(\delta(F) \ge 2\) and F must contain at least two \(C_3\) which do not share a vertex and are not incident to a \(C_3\). There are four
graphs satisfying these conditions, as shown in Figure 3, each with a red-blue coloring that is \((2K_2, H_5)\)-good (dotted line in red color). For all F, \(F \leftrightarrow (2K_2, H_5)\), so \(r^*(2K_2, H_5) \ge 10\). Since \(H_5 \subseteq H_8\), by (2) we obtain \(r^*(2K_2, H_8) \ge 10\).
Theorem 4. \(r^*(2K_2, H_6) = 9\).
Proof. We know that \(r(2K_2, H_6) = 6\). Note that \(C_3 \subseteq H_5\). To show the upper bound, let \(F = M_6\) with \(M_6\) be a Möbius ladder with six vertices. Observe that F is a 3-regular graph and contains two isomorphic \(C_3\). It is easy to verify that \(H_6 \subseteq F - v\) for every \(v \in V(F)\) and \(H_6 \subseteq F - C_3\) for every \(C_3\) in F. Hence, Lemma 1 implies \(F \to (2K_2, H_6)\), so \(r^*(2K_2, H_6) \le 9\).
Figure 4 Graphs F that satisfy the conditions for the lower bound of Theorem 4.
To show the lower bound, we must consider all graphs F with v(F) = 6 and e(F) = 8. According to Lemma 2 and 3, \(\delta(F) \ge 2\) and F must contain at least two \(C_3\) which do not share a vertex and are not incident to a \(C_3\). There are only two graphs satisfying these conditions, as shown in Figure 4, with red-blue coloring that are \((2K_2, H_6)\)-good (the red color in dotted line). Hence, \(F \nrightarrow (2K_2, H_6)\) for both F, so \(r^*(2K_2, H_6) \ge 9\).
Theorem 5. \(r^*(2K_2, H_9) = 8\).
Proof. We know that \(r(2K_2, H_9) = 6\). Note that \(C_4 \subseteq H_9\). To show the upper bound, let \(F' = M_6\) with \(M_6\) be a Möbius ladder with six vertices. Consider F = F' - e with e is an edge belonging to \(C_6\) in F'. Observe that F is a \(C_3\)-free and all vertices in F have degree either 2 or 3. Suppose u is a vertex with d(u) = 2 and v with d(v) = 3. It is clear that \(H_9 \subseteq F - v \subseteq F - u\). Hence, Lemma 1 implies \(F \to (2K_2, H_9)\), so \(r^*(2K_2, H_9) \le 8\).
To show the lower bound, we must consider all graphs F with v(F) = 6 and e(F) = 7. According to Lemma 2 and 3, \(\delta(F) \ge 2\) and F must contain at least two \(C_4\) which do not share a vertex and are not incident to a \(C_3\). However, there is no graph satisfying these conditions, so \(r^*(2K_2, H_9) \ge 8\).
Theorem 6. \(r^*(2K_2, H_{12}) = 12\).
Proof. We know that ݎ)2ܭଶ, ܪଵଶ)=6. Note that ܥସ ⊆ ܪଵଶ. To show the upper bound, consider ܨ=ܭ − 3ܭଶ. Observe that ܨ is a 4-regular graph and all ܥଷ in ܨ are isomorphic. It can be verified that ܪଵଶ ⊆ܨ−ݒ for every ݒ ∋ ܸ)ܨ (and ܪଵଶ ⊆ܨ−ܥଷ for every ܥଷ in ܨ. Hence, Lemma 1 implies ܨ) → 2ܭଶ, ܪଵଶ), so 12. ≥ (ଵଶܪ ,ଶܭ2)∗ݎ
To show the lower bound, we must consider all graphs ܨ with ݒ)ܨ = (6 and ݁(ܨ = (11. According to Lemmas 2 and 3, ߜ)ܨ ≤ (2 and ܨ must contain at least two ܥସ which do not share a vertex and are not incident to a ܥଷ. There are four graphs ܨ satisfying these conditions, namely, ܨ is isomorphic to ܭ − (ܥଷ ∪ ܭଶ), ܭ − ܲହ, ܭ −) ܲସ ∪ ܭଶ), or ܭ − 2ܲଷ. If ܨ=ܭ −) ܥଷ ∪ ܭଶ) or − ܭ=ܨ If 5.) = ݒ)݀ with vertex a is ݒ with ݒ−ܨ⊇/ ଵଶܪ then ,ହܲ − ܭ=ܨ (ܲସ ∪ ܭଶ) or ܨ=ܭ − 2ܲଷ, then ܪଵଶ ⊈ܨ−ܥଷ for any ܥଷ in each ܨ. Hence, Lemma 1 implies ܨ) ↛ 2ܭଶ, ܪଵଶ) for all ܨ, so ݎ)∗2ܭଶ, ܪଵଶ) ≥ 12.
12. = (ଵଵܪ ,ଶܭ2)∗ݎ 7. Theorem
Proof. We know that ݎ)2ܭଶ, ܪଵଵ)=6. To show the upper bound, consider −ܨ⊇ݑ−ܨ⊇ ଵଵܪ and 5) = ݑ)݀ with ݑ vertex a is there ܨ In .ଷ,ଵܭ − ܭ=ܨ ݒ for any ݒ in ܨ. Furthermore, there is a ܭସ in ܨ and all vertices ݒ ∋ ܸ)ܭସ) are adjacent to ݑ and one is adjacent to vertex ݔ with ݀(ݔ = (2. There are five kinds of ܥଷ in ܨ, namely, ܥଷ involving ݑ and two ݒ not adjacent to ݔ, ܥଷ involving ݑ and two ݒ one is adjacent to ݔ, ܥଷ involving three ݒ not adjacent to ݔ, ܥଷ involving three ݒ one is adjacent to ݔ, and ܥଷ involving ݔ. It can be verified that for every kind of ܥଷ, ܪଵଶ ⊆ܨ−ܥଷ. Hence, Lemma 1 implies 12. ≥ (ଵଵܪ ,ଶܭ2)∗ݎ so ,)ଵଵܪ ,ଶܭ2) → ܨ
Before proving the lower bound, consider ܨ′ = ܭ − 2ܲଶ. It is clear that ܪଵଵ ⊈ ܨ′ − ݒ for vertex ݒ with ݀(ݒ = (5. To show the lower bound, we must consider all graphs ܨ with ݒ)ܨ = (6 and ݁(ܨ = (11. According to Lemma 2, ߜ)ܨ ≤ (2. However, all ܨ that satisfy these conditions are subgraphs of ܨ′. Therefore, Lemma 1 implies ܨ) ↛ 2ܭଶ, ܪଵଵ) for all ܨ. Hence ݎ)∗2ܭଶ, ܪଵଵ) ≥ 12.
11. = (ଵଷܪ ,ଶܭ2)∗ݎ=(ଵܪ ,ଶܭ2)∗ݎ 8. Theorem
Proof. We know that ݎ)2ܭଶ, ܪଵ) = ݎ)2ܭଶ, ܪଵଷ)=6. Note that ܪଵ = ܥହ ⊆ ܪଵଷ. To show the upper bound, consider ܨ=ܭ −) ܲସ ∪ ܭଶ). All vertices in ܨ have degree either 3 or 4. For ݑ is a vertex with ݀(ݑ = (4, ܪଵଷ ⊆ܨ−ݑ⊇ܨ− ݒ for every ݒ in ܨ. Furthermore, there are two different ܥଷ in ܨ, namely, ܥଷ involving three vertices with degree 4 and ܥଷ involving two vertices with degree 3 and a vertex with degree 4. It can be verified that for both kinds of ܥଷ,
\(H_{13} \subseteq F - C_3\). Hence, Lemma 1 implies \(F \to (2K_2, H_{13})\), so \(r^*(2K_2, H_{13}) \le 11\). Since \(H_{10} \subseteq H_{13}\), by (2) we obtain \(r^*(2K_2, H_{10}) \le 11\).
To show the lower bound, we must consider all graphs F with v(F) = 6 and e(F) = 10. According to Lemma 4, \(\delta(F) \ge 3\). There are four graphs F satisfying these conditions, namely F is isomorphic to \(K_6 - (C_3 \cup P_3)\), \(K_6 - (C_4 \cup K_2)\), \(K_6 - C_5\), or \(K_6 - 2P_6\). For all F, \(H \nsubseteq F - C_3\) for any \(C_3\) in each F. Thus, Lemma 1 implies \(F \nrightarrow (2K_2, H_{10})\) for all F, so \(r^*(2K_2, H_{10}) \ge 11\). Since \(H_{10} \subseteq H_{13}\), by (2) we obtain \(r^*(2K_2, H_{13}) \ge 11\).
Theorem 9. \(r^*(2K_2, H_{16}) = 12\).
Proof. We know that \(r(2K_2, H_{16}) = 6\). Note that \(C_5 \subseteq H_{16}\). To show the upper bound, consider \(F = K_6 - 3K_2\). Observe that F is a 4-regular graph and all \(C_3\) in F are isomorphic. It is easy to verify that \(H_{16} \subseteq F - v\) for every \(v \in V(F)\) and \(H_{16} \subseteq F - C_3\) for every \(C_3\) in F. Hence, Lemma 1 implies \(F \to (2K_2, H_{16})\), so \(r^*(2K_2, H_{16}) \le 12\).
To show the lower bound, we must consider all graphs F with v(F)=6 and e(F)=11. According to Lemma 4, \(\delta(F)\geq 3\). Furthermore, \(\Delta(F)\leq 4\) as if there is a vertex v with d(v)=5, then \(e(F-v)=11-5=6< e(H_{16})\). The only graph satisfying the above conditions is F isomorphic to either \(K_6-(P_4\cup K_2)\) or \(K_6-2P_3\). Note that \(\Delta(H_{16})=4\). For both F, \(H_{16}\nsubseteq F-v\) since \(\Delta(F-v)=3\) for \(v\in V(F)\) with d(v)=4. Hence, Lemma 1 implies \(F\nrightarrow (2K_2,H_{16})\), so \(r^*(2K_2,H_{16})\geq 12\).
Theorem 10. \(r^*(2K_2, H_{17}) = 13\).
Proof. We know that \(r(2K_2, H_{17}) = 6\). Note that \(C_5 \subseteq H_{17}\). To show the upper bound, consider \(F = K_6 - 2K_2\). All vertices in F have degree either 4 or 5. For u is a vertex with d(u) = 5, \(H_{17} \subseteq F - u \subseteq F - v\) for every v in F. Furthermore, there are two different \(C_3\) in F, namely, \(C_3\) involving two vertices with degree 5 and a vertex with degree 4 and \(C_3\) involving two vertices with degree 4 and a vertex with degree 5. It can be verified that for both kinds of \(C_3\), \(H_{17} \subseteq F - C_3\). Hence Lemma 1 implies \(F \to (2K_2, H_{17})\), so \(r^*(2K_2, H_{17}) \le 13\)
To show the lower bound, we must consider all graphs F with v(F)=6 and e(F)=12. According to Lemma 4, \(\delta(F)\geq 3\). There are four graphs F satisfying these conditions, namely F is isomorphic to \(K_6-3K_2\), \(K_6-(P_3\cup K_2)\), \(K_6-2P_4\), or \(K_6-C_3\). If \(F=K_6-3K_2\), then \(H_{17}\nsubseteq F-C_3\) for any \(C_3\). If \(F=K_6-(P_3\cup K_2)\), then \(H_{17}\nsubseteq F-C_3\) with \(C_3\) involving three vertices with degree 4. If \(F=K_6-P_4\), then \(H_{17}\nsubseteq F-v\) with v of degree 5. If \(F=K_6-C_3\), then \(H_{17} \nsubseteq F - C_3\) with \(C_3\) involving three vertices with degree 5. Hence, Lemma 1 implies \(F \nrightarrow (2K_2, H_{17})\) for all F, so \(r^*(2K_2, H_{17}) \ge 13\).
Theorem 11. \(r^*(2K_2, H_{15}) = 14\).
Proof. We know that \(r(2K_2, H_{14}) = 6\). To show the upper bound, consider \(F = K_6 - K_2\). All vertices in F have degree either 4 or 5. For u is a vertex with d(u) = 5, \(H_{15} \subseteq F - u \subseteq F - v\) for every \(v \in V(F)\). Furthermore, there are two different \(C_3\) in F, namely, \(C_3\) involving three vertices with degree 5 and \(C_3\) involving two vertices with degree 5 and a vertex with degree 4. It can be verified that for both kinds of \(C_3\), \(H_{15} \subseteq F - C_3\). Hence, Lemma 1 implies \(F \to (2K_2, H_{15})\), so \(r^*(2K_2, H_{15}) \le 14\).
To show the lower bound, we must consider all graphs F with v(F) = 6 and e(F) = 13. The only graph satisfying these conditions is F isomorphic to either \(K_6 - P_3\) or \(K_6 - 2K_2\). If \(F = K_6 - P_3\), then \(H_{15} \nsubseteq F - C_3\) with \(C_3\) involving three vertices with degree 5. If \(F = K_6 - 2K_2\), then \(H_{15} \nsubseteq F - C_3\) with \(C_3\) involving two vertices with degree 4 and a vertex with degree 5. Hence, Lemma 1 implies \(F \nrightarrow (2K_2, H_{15})\) for both F, so \(r^*(2K_2, H_{15}) \ge 14\).
We compile the restricted size Ramsey number for \(2K_2\) versus any graph of order five with no isolates in Table 1.
| \(r^*\) | \(H_1\) | \(H_2\) | \(H_3\) | \(H_4\) | \(H_5\) | \(H_6\) | \(H_7\) | \(H_8\) |
|---|---|---|---|---|---|---|---|---|
| 2K2 | 6 | 8 | 12 | 6 | 10 | 9 | 12 | 10 |
| [9] | [9] | [9] | [9] | Th.3 | Th.4 | [11] | Th.3 | |
| \(r^*\) | \(H_9\) | \(H_{10}\) | \(H_{11}\) | \(H_{12}\) | \(H_{13}\) | \(H_{14}\) | \(H_{15}\) | \(H_{16}\) |
| 2K2 | 8 | 11 | 12 | 12 | 11 | 13 | 14 | 12 |
| Th.5 | Th.8 | Th.7 | Th.6 | Th.8 | [11] | Th.11 | Th.9 | |
| \(r^*\) | \(H_{17}\) | \(H_{18}\) | \(H_{19}\) | \(H_{20}\) | \(H_{21}\) | \(H_{22}\) | \(H_{23}\) | |
| 2K2 | 13 | 15 | 13 | 14 | 15 | 15 | 21 | |
| Th.10 | [11] | [11] | [11] | [11] | [11] | [11] |
Table 1 Compilation of \(r^*(2K_2, H)\) with H is a graph that has no isolates of order five.
4 Conclusion
In this paper we gave the complete list of the exact values of the restricted size Ramsey number for \(2K_2\) versus any graph of order five with no isolates. For further research:
1. Find the size Ramsey number of \(\hat{r}(2K_2, H)\) for all H in Figure 1 except \(H_{23}\).
2. Find the restricted size Ramsey number ݎ)∗2ܭଶ, ܪ (with ܪ is a graph of order six for which ݎ)∗2ܭଶ, ܪ (is not yet given in [5].
Acknowledgements
The authors would like to thank the referees for their careful reading of the manuscript and their valuable suggestions. This research was partially funded by a research grant from the Program Penelitian Unggulan Perguruan Tinggi, Ministry of Research, Technology and Higher Education, Indonesia.