Maya Nabila^∗a , Hilda Assiyatunb,c, Edy Tri Baskorob,c

mayanabila@students.itb.ac.id, hilda@math.itb.ac.id, ebaskoro@itb.ac.id

Let F, G and H be simple graphs. The notation F → (G, H) means that for any red-blue coloring on the edges of graph F, there exists either a red copy of G or a blue copy of H. A graph F is called a Ramsey (G, H)-minimal graph if it satisfies two conditions: (i) F → (G, H) and (ii) F − e 9 (G, H) for any edge e of F. In this paper, we give some finite and infinite classes of Ramsey (C4, K1,n)-minimal graphs for any n ≥ 3.

Keywords: Ramsey minimal graph, cycle, star Mathematics Subject Classification : 05C55, 05D10

DOI: 10.5614/ejgta.2022.10.1.20

1. Introduction

All graphs in this paper are simple. For any three graphs F, G and H, the notation of F → (G, H) to mean that for any red-blue coloring on the edges of F, there exists a red copy of G or a blue copy of H.

Received: 27 December 2021, Revised: 7 April 2022, Accepted: 14 April 2022.

^aDoctoral Program of Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia

^bCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia

^cCollaborative Research Center for Graph Theory and Combinatorics, Indonesia

^∗Corresponding author

Definition 1.1. A graph F is called a Ramsey graph for a pair of graphs (G, H) if F satisfies that F → (G, H).

Definition 1.2. A graph F is called a Ramsey (G, H)-minimal if F satisfies the following conditions:

• (i) F → (G, H), and
• (ii) F − e 9 (G, H), for any e ∈ E(F).

The set of all Ramsey (G, H)-minimal graphs will be denoted by R(G, H).

The pair (G, H) is called a Ramsey-finite if R(G, H) is finite. Otherwise, the pair (G, H) is called Ramsey-infinite. The study of Ramsey minimal graphs was initiated by Burr et al. [3]. The problem of characterizing or determining all Ramsey (G, H)-minimal graphs for a certain pair of G and H is a challenging problem.

Burr et al. [2] showed that for an arbitrary graph G, the pair (mK2, G) is Ramsey-finite. Neset ˇ ˇril and Rodl proved that if both ¨ G and H are 3-connected or if G and H are forest and neither of which is a union of stars, then the pair (G, H) is Ramsey-infinite [7]. Next, Baskoro et al. [1] determined the graphs in R(K1,2, C4). In 2015, Mushi and Baskoro [6] gave necessary and sufficient conditions for all members of R(3K2, K1,n) for each n ≥ 3. Furthermore, for 3 ≤ n ≤ 7 they were able to list all Ramsey (3K2, K1,n)-minimal graphs of order at most 10 vertices. In the same year, Wijaya et al. [5] determined all non-isomorphic Ramsey (2K2, K4)-minimal graphs of order at least 9. Furthermore, they also gave a general class graph which belong to R(2K2, Kn), for n ≥ 3. Nisa et al. [9] gave some graphs in R(C6, K1,2). In 2021, Nabila and Baskoro [8] gave some Ramsey (Cn, K1,2)-minimal graphs for n ∈ {5, 6, 8}. In the same year, Hadiputra and Silaban [4] studied an infinite family of graphs that belongs to R(K1,2, C4). In 2022, Nabila et al. [10] gave some Ramsey (Cn, K1,2)-minimal graphs for any n ∈ [7, 10] and construct Ramsey (Cn, K1,2)-graphs from the well-known Harary graph, for any integer n ≥ 6.

In this paper, we construct some new finite and infinite classes of graphs that belong to the set R(C4, K1,n) for any n ≥ 3.

2. Main Results

Our main results will be divided into two sections. In the first section, we present some finite classes of Ramsey (C4, K1,n)-minimal graphs. The second section, we propose some infinite classes of such Ramsey minimal graphs.

For any vertex x ∈ V and A ⊂ V , let us denote by (x, A) the set of all edges connecting x and all vertices of A. This set can also be denoted by (A, x). Throughout the paper, we define [a, b] = {x ∈ N|a ≤ x ≤ b}, except in the proof Theorem 2.2, we use the notation for a different thing, but the context is clear.

2.1. Some finite classes of graph in R(C4, K1,n)

In this section, we give some finite class of graphs which belongs to R(C4, K1,n) for any integer n ≥ 3.

Definition 2.1. For any positive integer n ≥ 3, H(n) is a graph with the vertex-set and edge-set:

\[\begin{array}{lll} V & = & \{c_i, v_j \mid i \in [1, 3], \ j \in [1, 2n-1]\} & \text{and} \\ E & = & \{c_1 v_i, c_2 v_i, c_3 v_j | \ i \in [1, 2n-1], j \in [1, n+2]\}. \end{array}\]

In the following we show that the graph H(n) is a Ramsey (C4, K1,n)-minimal graph for any n ≥ 3.

Theorem 2.1. For any integer n ≥ 3, H(n) ∈ R(C4, K1,n).

Proof. Let α be any red-blue coloring of the edges of H(n) with no blue K1,n. Let W = {v ∈ V | vc1, vc² ∈ E}. Let A = {v ∈ V | vc1, vc2, vc³ ∈ E} and B = W\A. Since d(c1) = 2n − 1, then there are at most n − 1 blue edges incident to c1. Let S = {v ∈ W | c1v is red} and T = {v ∈ W | c1v is blue}. Then |S| ≥ n and |T| ≤ n − 1.

Now, consider the edges incident to c2. Since there is no blue K1,n, there are at most n−1 blue edges connecting c² and vertices of W. If there are at most n − 2 blue edges connecting c² to S then it creates a red C4. Thus, there are exactly n − 1 blue edges connecting c² with the vertices of S and no blue edges connecting T with c2.

Next, consider the edges incident to c3. Clearly, there are at most n − 1 blue edges and at least 3 red edges connecting between A and c3. If there are two red edges connecting T ∩ A and c³ then a red copy of C⁴ occurs (involving c2, c³ and T). Similarly, if there are two red edges connecting S ∩A and c³ then a red copy of C⁴ occurs (involving c1, c³ and S). Therefore, H(n) → (C4, K1,n).

To show the minimality, consider G ∼= H(n) − e for any edge e ∈ H(n). Up to isomorphism, we consider three cases:

• (i) Let e = c1v¹ ∈ (c1, A). Then, consider a red-blue coloring on G with all edges in the set (c1, A\{v2, v3}) ∪ (c2, B\{v2n−1}) ∪ (c2, {v2, v3, v4})∪ (c3, A\{v1, v2, v3}) are blue and the remaining edges are red.
• (ii) Let e = c2v2n−¹ ∈ (c2, B). Then, consider a red-blue coloring on G with all edges in the set {(c1, A\{v1, v2, v3}) ∪ (c2, B\{v2n−1)} ∪ (c2, {v2, v3, v4}) ∪ (c3, A\{v3, v4, v5})} are blue and the remaining edges are red.
• (iii) Let e = c3v¹ ∈ (c3, A). Then, consider a red-blue coloring on G with all edges in the set {(c1, A\{v1, v2, v3}) ∪ (c2, B\{v2n−1)} ∪ (c2, {v1, v2, v4}) ∪ (c3, A\{v2, v4})} are blue and the remaining edges are red.

Therefore, in such a coloring, there is neither red copy of C⁴ nor blue copy of K1,n. Thus, G 9 (C4, K1,n). As a consequence, H(n) is a Ramsey (C4, K1,n)-minimal graph.

Let t be any natural number, define a theta-path graph G[a1, ..., a^t ] with aⁱ ≥ 3 for i ∈ [1, t] as follows.

Definition 2.2. The theta-path graph of length t, denoted by G[a1, a2, ..., a^t ], is the graph with the vertex set and the edge set:

\[V = \{c_1, c_2, ..., c_{t+1}\} \cup A_1 \cup ... \cup A_t \text{ with } |A_i| = a_i \text{ and } A_i = \{u_{i,1}, ..., u_{i,a_i}\}\] \[\text{for } i \in [1, t]\] \[E = \{(c_i, A_i), (A_i, c_{i+1}) | i \in [1, t]\}.\]

Note that if t = 1, then \(G[a_1] \cong K_{2,a_1}\).

Let \(\alpha\) be any red-blue coloring on the edges of the theta-path graph \(G[a_1,a_2,...,a_t]\). For any \(i\in [1,t]\), let \(b_i^+\) be the number of blue edges in \((c_i,A_i)\) under \(\alpha\). For any \(i\in [2,t+1]\) let \(b_i^-\) be the number of blue edges in \((A_{i-1},c_i)\) under \(\alpha\). We use the notation \([b_1^+,b_2^-|b_2^+,b_3^-|\ldots|b_{t-1}^+,b_t^-|b_t^+,b_{t+1}^-|\) for the coloring \(\alpha\) if there are exactly \(b_i^+\) blue edges in \((c_i,A_i)\) and \(b_i^-\) blue edges in \((A_{i-1},c_i)\) for any i in \(\alpha\). Additionally, if the number of vertices of \(A_i\) incident to blue edges is \(b_i^++b_{i+1}^-\) for every \(i\in [1,t]\), then the coloring \(\alpha\) is called maximal.

For example, Figure 1 represents a red blue coloring [4,2|3,0] (left) and a maximal red blue coloring [5,2|4,1] (right) in G[7,5]. Note that, in general, the colorings with the notation \([b_1^+,b_2^-|b_2^+,b_3^-|\dots|b_{t-1}^+,b_t^-|b_t^+,b_{t+1}^-]\) may not be unique.

Figure 1. Some red-blue colorings in the theta-path graph G[7, 5].

2.1.1. The theta-path graph of length 1.

In this section, we present the theta-path graph of length one which is in \(\mathcal{R}(C_4, K_{1,n})\).

Theorem 2.2. For any integer \(n \geq 3\), the theta-path graph \(G[2n] \in \mathcal{R}(C_4, K_{1,n})\).

Proof. Let G=G[2n] for any fixed integer \(n\geq 3\). First, we will show that \(G\to (C_4,K_{1,n})\). Consider any red-blue coloring \(\alpha\) on the edges of G with containing no blue \(K_{1,n}\). We will show that there is a red \(C_4\) in G. Let \(\alpha\) be a coloring \([b_1^+,b_2^-]\) for some integers \(b_1^+\) and \(b_2^-\). The number of vertices in \(A_1\) incident to blue edges is denoted by \(n_1\). Since there is no blue \(K_{1,n}\) in G then \(b_1^+\leq n-1, b_2^-\leq n-1\), and \(b_1^++b_2^-=n_1\leq 2n-2\). Thus, there exists a red \(C_4\) in G composed by two vertices in \(A_1\) together with \(c_1\) and \(c_2\).

Next, we will show the minimality, that is, \(G-e \nrightarrow (C_4,K_{1,n})\) for any edge e. Let \(e \in (c_1,A_1)\) or \((A_1,c_2)\), then consider the maximal red-blue coloring \(\alpha_1 \cong [n-1,n-1]\) on G such that \(\alpha_1(e)\) is red. By considering the restriction of the coloring \(\alpha_1\) on G-e, we obtain that there is neither blue copy of \(K_{1,n}\) nor red copy of \(C_4\) in G-e. Thus, \(G-e \nrightarrow (C_4,K_{1,n})\). Therefore, G is a Ramsey \((C_4,K_{1,n})\)-minimal graph. \(\square\)

2.1.2. The theta-path graph of length two.

In this section, we construct the theta-path graph of length two which is in \(\mathcal{R}(C_4, K_{1,n})\).

Theorem 2.3. Let n and k be integers, with \(n \ge 3\) and \(1 \le k \le \lfloor (n-1)/2 \rfloor\). Then, the theta-path graph \(G[a_1, a_2]\) in \(\mathcal{R}(C_4, K_{1,n})\), where \(a_1 = 2n - k\) and \(a_2 = n + k\).

Proof. Let G = G[2n - k, n + k] for any fixed integers \(n \ge 3\) and \(k \in [1, \lfloor (n-1)/2 \rfloor]\). First, we will show that \(G \to (C_4, K_{1,n})\). Consider any red-blue coloring \(\alpha\) on the edges of G with containing no blue \(K_{1,n}\). We will show there is a red \(C_4\) in G. Let \(\alpha\) be a coloring \([b_1^+, b_2^-|b_2^+, b_3^-]\) for some integers \(b_1^+, b_2^-, b_2^+\) and \(b_3^-\).

For i=1,2, denote by \(n_i\) the number of vertices in \(A_i\) incident to blue edges. Since there is no blue \(K_{1,n}\) in G then \(b_1^+ \leq n-1\), \(b_2^- + b_2^+ \leq n-1\), \(b_3^- \leq n-1\), \(n_1 \leq 2n-k\), and \(n_2 \leq n+k\). However, \(n_1 \geq 2n-k-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_1\) together with \(c_1\) and \(c_2\), or two vertices in \(A_2\) together with \(c_2\) and \(c_3\). Thus, \(2n-k-1 \leq n_1 \leq 2n-k\).

Since \(2n-k-1 \le n_1 \le 2n-k\), then \(b_2^- \ge (2n-k-1)-(n-1)=n-k\). Since \(b_2^- + b_2^+ \le n-1\) then \(b_2^+ \le (n-1)-(n-k)=k-1\). But, since \(b_2^+ \le k-1\) and \(b_3^- \le n-1\) then \(n_2 \le (n-1)+(k-1)=n+k-2\). Therefore, there is a red \(C_4\) in G.

Next, we will show the minimality, that is, \(G-e \rightarrow (C_4,K_{1,n})\) for any edge \(e \in G\). If \(e \in (c_1,A_1)\) or \((A_1,c_2)\) then consider the maximal red-blue coloring \(\alpha_1 \cong [n-1,n-k-1|k,n-1]\) on G such that \(\alpha_1(e)\) is red. By considering the restriction of the coloring \(\alpha_1\) on G-e, we obtain that there is neither blue copy of \(K_{1,n}\) nor red copy of \(C_4\) in G-e.

If \(e \in (c_2, A_2)\) or \((A_2, c_3)\) then consider the maximal red-blue coloring \(\alpha_2 \cong [n-1, n-k|k-1, n-1]\) on G such that no two blue edges incident to the same vertex of \(A_i\), for i=1,2, and \(\alpha_2(e)\) is red. By restricting \(\alpha_2\) on G-e, we obtain that there is neither blue \(K_{1,n}\) nor red \(C_4\) in G-e. Thus, \(G-e \nrightarrow (C_4, K_{1,n})\). Therefore, G is a Ramsey \((C_4, K_{1,n})\)-minimal graph. \(\square\)

2.1.3. The theta-path graph of length 3.

In this section, we give the theta-path graph of length 3 which is in \(\mathcal{R}(C_4, K_{1,n})\).

Theorem 2.4. Let n and k be integers, with \(n \ge 3\) and \(0 \le k \le \lfloor (n-1)/2 \rfloor\). Then, the theta-path graphs G[n+k-1,2n-k,n+1], G[2n-k,n+k-1,n+1], and G[2n-k,n+1,n+k-1] are in \(\mathcal{R}(C_4,K_{1,n})\).

Proof. Let \(G \cong G[n+(k-1), 2n-k, n+1]\) for any fixed integers \(n \geq 3\) and \(2 \leq k \leq \lfloor (n-1)/2 \rfloor\). First, we will show that \(G \to (C_4, K_{1,n})\). Consider any red-blue coloring \(\alpha\) on the edges of G with containing no blue \(K_{1,n}\). We will show that there is a red \(C_4\) in G. Let \(\alpha\) be a coloring \([b_1^+, b_2^-|b_2^+, b_3^-|b_3^+, b_4^-]\) for some integers \(b_i^+, b_{i+1}^-\) where \(i \in [1,3]\). For \(i \in [1,3]\), denote by \(n_i\) the number of vertices in \(A_i\) incident to blue edges. Since there is no blue \(K_{1,n}\) in G then \(b_1^+ \leq n-1\), \(b_2^- + b_2^+ \leq n-1\), \(b_3^- + b_3^+ \leq n-1\), and \(b_4^- \leq n-1\). However, \(n_1 \geq n+(k-1)-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_1\) together with \(c_1\) and \(c_2\), or two vertices in \(A_2\) together with \(c_2\) and \(c_3\). Thus, \(n+(k-1)-1\leq n_1\leq n+(k-1)\).

Since \(n+(k-1)-1\leq n_1\leq n+(k-1)\) then \(b_2^-\geq (n+k-2)-(n-1)=k-1\). Since \(b_2^-+b_2^+\leq n-1\) then \(b_2^+\leq (n-1)-(k-1)=n-k\). However, \(n_2\geq 2n-k-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_2\) together with \(c_2\) and \(c_3\), or two vertices in \(A_3\) together with \(c_3\) and \(c_4\). Thus, \(2n-k-1\leq n_2\leq 2n-k\). Since \(2n-k-1\leq n_2\leq 2n-k\), then \(b_2^+\geq (2n-k-1)-(n-k)=n-1\). Since \(b_3^-+b_3^+\leq n-1\) then \(b_3^+\leq (n-1)-(n-1)=0\). But, since \(b_3^+\leq 0\) and \(b_4^-\leq 0+(n-1)=n-1\), then \(n_3\leq n-1\). Therefore, there is a red \(C_4\) in \(C_4\) composed by two vertices in \(C_4\) with \(C_4\) and \(C_4\).

Next, we will show the minimality, that is, \(G-e \to (C_4,K_{1,n})\) for any edge \(e \in G\). If \(e \in (c_1,A_1)\) or \((A_1,c_2)\) then consider the maximal red-blue coloring \(\alpha_1 \cong [n-1,k-2|n-k+1,n-2|1,n-1]\) on G such that \(\alpha_1(e)\) is red. If \(e \in (c_2,A_2)\) or \((A_2,c_3)\) then consider the maximal red-blue coloring \(\alpha_2 \cong [n-1,k-1|n-k,n-2|1,n-1]\) on G such that \(\alpha_2(e)\) is red. If \(e \in (c_3,A_3)\) or \((A_3,c_4)\) then consider the maximal red-blue coloring \(\alpha_3 \cong [n-1,k-1|n-k,n-1|0,n-1]\) on G such that \(\alpha_3(e)\) is red. By considering the restriction of the coloring \(\alpha_1,\alpha_2\), and \(\alpha_3\) on G-e. Thus, \(G-e \nrightarrow (C_4,K_{1,n})\). Therefore, G is a Ramsey \((C_4,K_{1,n})\)-minimal graph.

If \(G \cong G[2n-k,n+k-1,n+1]\) or \(G \cong G[2n-k,n+1,n+k-1]\) then the proofs are similar.

Theorem 2.5. Let n and k be integers, with \(n \ge 3\) and \(1 \le k \le \lfloor (n-1)/2 \rfloor\). Then, the theta-path graph G[2n-k,n,n+k] in \(\mathcal{R}(C_4,K_{1,n})\).

Proof. Let G = G[2n-k,n,n+k] for any fixed integers \(n \geq 3\) and \(1 \leq k \leq \lfloor (n-1)/2 \rfloor\). First, we will show that \(G \to (C_4,K_{1,n})\). Consider any red-blue coloring \(\alpha\) on the edges of G with containing no blue \(K_{1,n}\). We will show there is a red \(C_4\) in G. Let \(\alpha\) be a coloring \([b_1^+,b_2^-|b_2^+,b_3^-|b_3^+,b_4^-]\) for some integers \(b_i^+,b_{i+1}^-\) where \(i \in [1,3]\).

Since there is no blue \(K_{1,n}\) in G then \(b_1^+ \le n-1\), \(b_i^- + b_i^+ \le n-1\) for \(i=2,3, b_4^- \le n-1\), \(n_1 \le 2n-k, n_2 \le n\), and \(n_3 \le n+k\). However, \(n_1 \ge 2n-k-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_1\) together with \(c_1\) and \(c_2\), or two vertices in \(A_2\) together with \(c_2\) and \(c_3\). Thus, \(2n-k-1 \le n_1 \le 2n-k\).

Since \(2n-k-1 \le n_1 \le 2n-k\) then \(b_2^- \ge (2n-k-1)-(n-1)=n-k\). Since \(b_2^- + b_2^+ \le n-1\) then \(b_2^+ \le (n-1)-(n-k)=k-1\). However, \(n_2 \ge n-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_2\) together with \(c_2\) and \(c_3\), or two vertices in \(A_3\) together with \(c_3\) and \(c_4\). Thus, \(n-1 \le n_2 \le n\). Since \(n-1 \le n_2 \le n\), then \(b_3^- \ge (n-1)-(k-1)=n-k\). Since \(b_3^- + b_3^+ \le n-1\) then \(b_3^+ \le (n-1)-(n-k)=k-1\). But, since \(b_3^+ \le k-1\) and \(b_4^- \le n-1\) then \(n_3 \le (k-1)+(n-1)=n+k-2\). Therefore, there is a red \(C_4\) in G composed by two vertices in \(A_3\) with \(c_3\) and \(c_4\).

Next, we will show the minimality, that is, \(G-e \nrightarrow (C_4,K_{1,n})\) for any edge \(e \in G\). If \(e \in (c_1,A_1)\) or \((A_1,c_2)\) then consider the maximal red-blue coloring \(\alpha_1 \cong [n-1,n-k-1|k,n-k-1|k,n-1]\) on G such that \(\alpha_1(e)\) is red. If \(e \in (c_2,A_2)\) or \((A_2,c_3)\) then consider the maximal red-blue coloring \(\alpha_2 \cong [n-1,n-k|k-1,n-k-1|k,n-1]\) on G such that \(\alpha_2(e)\) is red. If \(e \in (c_3,A_3)\) or \((A_3,c_4)\) then consider the maximal red-blue coloring \(\alpha_3 \cong [n-1,n-k|k-1,n-k|k-1,n-1]\) on G such that \(\alpha_3(e)\) is red. By considering the restriction of the coloring \(\alpha_1,\alpha_2\), and \(\alpha_3\) on G-e. Thus, \(G-e \nrightarrow (C_4,K_{1,n})\). Therefore, G is a Ramsey \((C_4,K_{1,n})\)-minimal graph. \(\Box\)

2.1.4. The theta-path graph with a longer length.

In this section, we present the theta-path graph of length k which is \(\mathcal{R}(C_4, K_{1,n})\), with \(4 \le k \le n+1\).

Theorem 2.6. Let n and k be integers, with \(n \geq 3\) and \(3 \leq k \leq n\). Then, the theta-path graph \(G[a_1, a_2, ..., a_{k+1}]\) in \(\mathcal{R}(C_4, K_{1,n})\), with \(a_1 = 2n - k\) and \(a_i = n + 1\) for \(i \in [2, k+1]\).

Proof. Let \(G = G[2n - k, a_2, ..., a_{k+1}]\) for any fixed integers \(n \ge 3\), \(2 \le k \le n\), where \(a_i = n+1\) for \(i \in [2, k+1]\). First, we will show that \(G \to (C_4, K_{1,n})\). Consider any red-blue coloring \(\alpha\)

on the edges of G with containing no blue \(K_{1,n}\). We will show there is a red \(C_4\) in G. Let \(\alpha\) be a coloring \([b_1^+, b_2^-|b_2^+, b_3^-|...|b_k^+, b_{k+1}^-|b_{k+1}^+, b_{k+2}^-|\) for some integers \(b_i^+, b_{i+1}^-\) with \(i \in [1, k+1]\). For \(i \in [1, k+1]\), denote by \(n_i\) the number of vertices in \(A_i\) incident to blue edges. Since there is no blue \(K_{1,n}\) in G then \(b_1^+ \leq n-1\), \(b_i^- + b_i^+ \leq n-1\) for \(i \in [2, k+1]\), \(b_{k+2}^- \leq n-1\), \(n_1 \leq 2n-k\), and \(n_i \leq n+1\) for \(i \in [2, k+1]\). However, \(n_1 \geq 2n-k-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_1\) together with \(c_1\) and \(c_2\), or two vertices in \(A_2\) together with \(c_2\) and \(c_3\). Thus, \(2n-k-1 \leq n_1 \leq 2n-k\).

Since \(2n-k-1 \le n_1 \le 2n-k\), then \(b_2^- \ge (2n-k-1)-(n-1)=n-k\). Since \(b_2^- + b_2^+ \le n-1\) then \(b_2^+ \le (n-1)-(n-k)=k-1\). However, \(n_2 \ge n\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_2\) together with \(c_2\) and \(c_3\), or two vertices in \(A_3\) together with \(c_3\) and \(c_4\). Thus, \(n \le n_2 \le n+1\). Since \(n \le n_2 \le n+1\), then \(b_3^- \ge n-(k-1)=n-k+1\). Since \(b_3^- + b_3^+ \le n-1\) then \(b_3^+ \le (n-1)-(n-k+1)=k-2\).

Since \(A_2, ..., A_{k+1}\) have the same number of vertices, then we obtain \(b_i^+ \le k - (i-1)\) and \(b_i^- \ge n - (k - (i-1))\) for \(0 \le i \le k+1\). However, for \(i \in [2,k]\) \(n_i \ge n\) since otherwise there exists a red \(0 \le i \le k+1\). However, for \(i \in [2,k]\) \(n_i \ge n\) since otherwise there exists a red \(0 \le i \le k+1\). Thus, \(i \le n \le i \le k+1\). Since \(i \le i \le k+1\) and \(i \le i \le n+1\). Since \(i \le i \le k+1\) and \(i \le i \le n+1\) and \(i \le i \le n+1\). Therefore, there is a red \(i \le i \le n+1\) together with \(i \le i \le n+1\). Therefore, there is a red \(i \le i \le n+1\) together with \(i \le i \le n+1\). Therefore, there is a red \(i \le i \le n+1\) together with \(i \le i \le n+1\). Therefore, there is a red \(i \le i \le n+1\).

Next, we will show the minimality, that is, \(G-e \nrightarrow (C_4,K_{1,n})\) for any edge \(e \in G\). Define \(\alpha_1 \cong [b_1^+,b_2^-|b_2^+,b_3^-|...|b_k^+,b_{k+1}^-|b_{k+1}^+,b_{k+2}^-]\) where \(b_1^+=n-1,b_i^-=n-k+(i-2),b_i^+=k-(i-1)\) with \(i \in [2,k+1]\), and \(b_{k+2}^-=n-1\). Next, for \(j \in [2,k+1]\) define \(\alpha_j \cong [d_1^+,d_2^-|d_2^+,d_3^-|...|d_k^+,d_{k+1}^-|d_{k+1}^+,d_{k+2}^-]\) where

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Let \(e \in (c_i, A_i)\) or \((A_i, c_{i+1})\) for some \(i \in [1, k+1]\), then consider the maximal red-blue coloring \(\alpha_i\) on G such that \(\alpha_i(e)\) is red. By considering the restriction of the coloring \(\alpha_i\) for \(i \in [1, k+1]\) on G - e. Thus, \(G - e \nrightarrow (C_4, K_{1,n})\). Therefore, G is a Ramsey \((C_4, K_{1,n})\)-minimal graph. \(\square\)

2.2. Some infinite classes of graphs in \(\mathcal{R}(C_4, K_{1,n})\)

In this section, we are going to construct some infinite classes of graphs which belong to \(\mathcal{R}(C_4, K_{1,n})\) for any integer \(n \geq 3\).

The first class is the theta-path graph \(G[2n-k, a_2, ..., a_{z+1}, n+k]\) of length z+2 for any \(z \ge 2\). The second class is the theta-path graph \(G[n+(k-1), a_2, ..., a_{z_1+1}, 2n-k, a_{z_1+3}, ..., a_{z_2+z_1+2}, n+1]\) of length \(z_1+z_2+3\) for any \(z_1, z_2 \ge 1\).

To illustrate these theta-path graphs, we give \(G[2n-k, a_2, ..., a_{z+1}, n+k]\) with n=4, k=1, and z=4 in Figure 2.

Theorem 2.7. Let n, k and z be integers, with \(n \ge 3\), \(2 \le k \le \lfloor (n-1)/2 \rfloor\) and \(z \ge 2\). Then, the theta-path graph \(G[2n-k, a_2, ..., a_{z+1}, n+k]\) in \(\mathcal{R}(C_4, K_{1,n})\), with \(a_i = n\) for \(i \in [2, z+1]\).

Figure 2. Graph G[7, 4, 4, 4, 4, 5].

Proof. Let \(G \cong G[2n-k,a_2,...,a_{z+1},n+k]\) for any fixed integers \(n \geq 3\), \(z \geq 1\) and \(k \in [1,\lfloor (n-1)/2 \rfloor]\). First, we will show that \(G \to (C_4,K_{1,n})\). Consider any red-blue coloring on the edges of G with containing no blue \(K_{1,n}\). We will show that there is a red \(C_4\) in G. Let G be a coloring \([b_1^+,b_2^-|b_2^+,b_3^-|...|b_z^+,b_{z+1}^-|b_{z+1}^+,b_{z+2}^-|b_{z+2}^+,b_{z+3}^-]\). For \(i \in [1,z+2]\), denote by \(n_i\) the number of vertices in \(A_i\) incident to blue edges.

Since there is no blue \(K_{1,n}\) in G then \(b_1^+ \le n-1\), \(b_2^- + b_2^+ \le n-1\), \(b_{z+3}^- \le n-1\), \(b_i^- + b_i^+ \le n-1\) for \(i \in [2,z+2]\), \(n_1 \le 2n-k\), \(n_i \le n\) for \(i \in [2,z+1]\), and \(n_{z+2} \le n+k\). However, \(n_1 \ge 2n-k-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_1\) together with \(c_1\) and \(c_2\), or two vertices in \(A_2\) together with \(c_2\) and \(c_3\). Thus, \(2n-k-1 \le n_1 \le 2n-k\).

Since \(2n-k-1 \le n_1 \le 2n-k\) then \(b_2^- \ge (2n-k-1)-(n-1)=n-k\). Since \(b_2^- + b_2^+ \le n-1\) then \(b_2^+ \le (n-1)-(n-k)=k-1\). However, \(n_2 \ge n-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_2\) together with \(c_2\) and \(c_3\), or two vertices in \(A_3\) together with \(c_3\) and \(c_4\). Thus, \(n-1 \le n_2 \le n\). Since \(n-1 \le n_2 \le n\), then \(b_3^- \ge (n-1)-(k-1)=n-k\). Since \(b_3^- + b_3^+ \le n-1\) then \(b_3^+ \le (n-1)-(n-k)=k-1\).

Since \(A_2, ..., A_{z+1}\) have the same number of vertices, then we obtain \(b_i^+ \le k-1\) and \(b_{i+1}^- \ge n-k\) for \(0 \le i \le z+1\). However, for \(i \in [2,z+1]\) i=1 and i=1 since otherwise there exists a red i=1 and i=1 and i=1 someone of i=1 and i=1 someone of i=1 and i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someone of i=1 someon

Next, we will show the minimality, that is, \(G - e \nrightarrow (C_4, K_{1,n})\) for any edge \(e \in G\). Now, define the labeling \(\alpha_1\) as follows:

\[\alpha_1 \cong [b_1^+, b_2^-|b_2^+, b_3^-|...|b_{z+1}^+, b_{z+2}^-|b_{z+2}^+, b_{z+3}^-],\]

where \(b_1^+=n-1, b_i^-=n-k-1, b_i^+=k\) with \(i\in[2,z+2]\), and \(b_{z+3}^-=n-1\). For \(j=2,3,\cdots,z+2,\) define

\[\alpha_j \cong [d_1^+, d_2^-|d_2^+, d_3^-|...|d_{z+1}^+, d_{z+2}^-|d_{z+2}^+, d_{z+3}^-],\]

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Let \(e \in (c_i, A_i)\) or \((A_i, c_{i+1})\) for some \(i \in [1, z+2]\), then consider the maximal red-blue coloring \(\alpha_i\) on G such that \(\alpha_i(e)\) is red. By considering the restriction of the coloring \(\alpha_i\) for

\(i \in [1, z+2]\) on G-e. Thus, \(G-e \nrightarrow (C_4, K_{1,n})\). Therefore, G is a Ramsey \((C_4, K_{1,n})\)-minimal graph. \(\Box\)

Theorem 2.8. Let \(n, k, z_1\) and \(z_2\) be integers, with \(n \ge 3\), \(2 \le k \le \lfloor \frac{n-1}{2} \rfloor\) and \(z_1, z_2 \ge 1\). Then, the theta-path graph \(G[n+(k-1), a_2, ..., a_{z_1+1}, 2n-k, a_{z_1+3}, ..., a_{z_2+z_1+2}, n+1]\) in \(\mathcal{R}(C_4, K_{1,n})\), with \(a_i = n\) for \(i \in [2, z_1 + 1] \cup [z_1 + 3, z_2 + z_1 + 2]\).

Proof. Let \(G = G[n + (k - 1), a_2, ..., a_{z_1 + 1}, 2n - k, a_{z_1 + 3}, ..., a_{z_2 + z_1 + 2}, n + 1]\) for any fixed integers \(n \ge 3\) and \(z_1, z_2 \ge 1\). First, we will show that \(G \to (C_4, K_{1,n})\). Consider any red-blue coloring on the edges of G with containing no blue \(K_{1,n}\). We will show that there is a red \(C_4\) in G. Let α be a coloring \([b_1^+, b_2^-|b_2^+, b_3^-|...|b_{z_1 + 1}^+, b_{z_1 + 2}^-|b_{z_1 + 2}^+, b_{z_1 + 3}^-|...|b_{m + 2}^+, b_{m + 3}^-|b_{m + 3}^+, b_{m + 4}^-]\) where \(m = z_1 + z_2\). For i ∈ [1, m + 3], denote by \(n_i\) the number of vertices in \(A_i\) incident to blue edges.

Since there is no blue \(K_{1,n}\) in G then \(b_1^+ \leq n-1\), \(b_2^- + b_2^+ \leq n-1\), \(b_{m+4}^- \leq n-1\), \(b_i^- + b_i^+ \leq n-1\) for \(i \in [2, m+3]\), \(n_1 \leq n+k-1\), \(n_i \leq n\) for \(i \in [2, z_1+1] \cup [z_1+3, m+2]\), \(n_{z_1+2} \leq 2n-k\), and \(n_{m+3} \leq n+1\). However, \(n_1 \geq n+k-2\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_1\) together with \(c_1\) and \(c_2\), or two vertices in \(A_2\) together with \(c_2\) and \(c_3\). Thus, \(n+k-2 \leq n_1 \leq n+k-1\).

Since \(n+k-2 \le n_1 \le n+k-1\), then \(b_2^- \ge (n+k-2)-(n-1)=k-1\). Since \(b_2^- + b_2^+ \le n-1\) then \(b_2^+ \le (n-1)-(k-1)=n-k\). However, \(n_2 \ge n-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_2\) together with \(c_2\) and \(c_3\), or two vertices in \(A_3\) together with \(c_3\) and \(c_4\). Thus, \(n-1 \le n_2 \le n\). Since \(n-1 \le n_2 \le n\), then \(b_3^- \ge (n-1)-(k-1)=n-k\). Since \(b_3^- + b_3^+ \le n-1\) then \(b_3^+ \le (n-1)-(n-k)=k-1\).

Since \(A_2, ..., A_{z_1+1}\) have the same number of vertices, then we obtain \(b_i^+ \le n-k\) and \(b_{i+1}^- \ge k-1\) for \(i \in [2,z_1+1]\) and j=i. However, for \(j \in [2,z_1+1]\), \(n_j \ge n-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_j\) together with \(c_j\) and \(c_{j+1}\), or two vertices in \(A_{j+1}\) together with \(c_{j+1}\) and \(c_{j+2}\). Thus, \(n-1 \le n_j \le n\).

Since \(b_{z_1+2}^- \ge k-1\), then \(b_{z_1+2}^+ \le (n-1)-(k-1)=n-k\). However, \(n_{z_1+2} \ge 2n-k-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_{z_1+2}\) together with \(c_{z_1+2}\) and \(c_{z_1+3}\), or two vertices in \(A_{z_1+3}\) together with \(c_{z_1+3}\) and \(c_{z_1+4}\). Thus, \(2n-k-1 \le n_{z_1+2} \le 2n-k\).

Since \(2n-k-1 \le n_{z_1+2} \le 2n-k\), then \(b_{z_1+3}^- \le (2n-k-1)-(n-k)=n-1\). Since \(b_{z_1+3}^- + b_{z_1+3}^+ \le n-1\) then \(b_{z_1+3}^+ \le (n-1)-(n-1)=0\). However, \(n_{z_1+3} \ge n-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_{z_1+3}\) together with \(c_{z_1+3}\) and \(c_{z_1+4}\), or two vertices in \(A_{z_1+4}\) together with \(c_{z_1+4}\) and \(c_{z_1+5}\). Thus, \(n-1 \le n_{z_1+3} \le n\).

Since \(A_{z_1+3},...,A_{m+2}\) have the same number of vertices, then we obtain \(b_i^+ \leq 0\) and \(b_{i+1}^- \geq n-1\) for \(i \in [z_1+3,m+2]\). However, for \(j \in [z_1+3,m+2]\), \(n_j \geq n-1\) since otherwise there exists a red \(C_4\) in G composed by two vertices in \(A_j\) together with \(c_j\) and \(c_{j+1}\), or two vertices in \(A_{j+1}\) together with \(c_{j+1}\) and \(c_{j+2}\). Thus, \(n-1 \leq n_j \leq n\).

Since \(b_{m+3}^+ \le k-1\) and \(b_{m+4}^- \le n-1\), then \(b_{m+3}^+ + b_{m+4}^- = n_{m+3} \le (0) + (n-1) = n-1\). Therefore, there is a red \(C_4\) in G composed by two vertices in \(A_{m+3}\) together with \(c_{m+3}\) and \(c_{m+4}\).

Next, we will show the minimality, that is, \(G - e \nrightarrow (C_4, K_{1,n})\) for any edge \(e \in G\). Now, define the labeling \(\alpha_1\) as follows:

\[\alpha_1 \cong [b_1^+, b_2^-|b_2^+, b_3^-|...|b_{z_1+1}^+, b_{z_1+2}^-|b_{z_1+2}^+, b_{z_1+3}^-|...|b_{m+2}^+, b_{m+3}^-|b_{m+3}^+, b_{m+4}^-],\]

where

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

For \(j \in [2, m+3]\), define

\[\alpha_i \cong [d_1^+, d_2^-|d_2^+, d_3^-|...|d_{z_1+1}^+, d_{z_1+2}^-|d_{z_1+2}^+, d_{z_1+3}^-|...|d_{m+2}^+, d_{m+3}^-|d_{m+3}^+, d_{m+4}^-],\]

where

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Let \(e \in (c_i, A_i)\) or \((A_i, c_{i+1})\) for some \(i \in [1, m+3]\), then consider the maximal red-blue coloring \(\alpha_i\) on G such that \(\alpha_i(e)\) is red. By considering the restriction of the coloring \(\alpha_i\) for \(i \in [1, m+3]\) on G-e. Thus, \(G-e \nrightarrow (C_4, K_{1,n})\). Therefore, G is a Ramsey \((C_4, K_{1,n})\)-minimal graph. \(\square\)

Acknowledgement

This research has been supported by the Indonesian Ministry of Education, Culture, Research and Technology under the Research grant of Pendidikan Magister menuju Doktor untuk Sarjana Unggulan (PMDSU).

References

• [1] E.T. Baskoro, L. Yulianti, and H. Assiyatun. Ramsey \((K_{1,2}, C_4)\)-minimal graphs, J. Combin. Math. Combin. Comput., 65 (2008), 79–90.
• [2] S.A. Burr, P. Erdős, R.J. Faudree, and R. H. Schelp, A class of Ramsey-finite graphs, In Proc. 9th SE Conf. on Combinatorics, Graph Theory and Computing, (1978), 171–178.
• [3] S.A. Burr, P. Erdős, and L. Lovász, On graphs of Ramsey type. Ars Combinatoria, 1(1) (1976), 167–190.
• [4] F.F. Hadiputra and D.R. Silaban, Infinite family of Ramsey \((K_{1,2}, C_4)\)-minimal graphs. Journal of Physics: Conference Series, 1722 (1) (2020), 012049.
• [5] K. Wijaya, E.T. Baskoro, H. Assiyatun, and D. Suprijanto, The complete list of Ramsey \((2K_2, K_4)\)-minimal graphs. Electronic Journal of Graph Theory and Applications (EJGTA), 3 (2) (2015), 216–227.
• [6] H. Muhshi and E.T. Baskoro, Matching-star Ramsey minimal graphs. Mathematics in Computer Science, 9 (4) (2015), 443–452.

• [7] J. Neset ˇ ˇril and Rodl, The structure of critical Ramsey graphs. Acta Mathematica Hungarica, ˝ 32 (3-4) (1978), 295–300.
• [8] M. Nabila and E.T. Baskoro, On Ramsey (Cn, H)-minimal graphs. In Journal of Physics: Conference Series, 1722 (1) (2021), 012052.
• [9] F. Nisa, D. Rahmadani, Purwanto, and H. Susanto, On Ramsey (P3, C6)-minimal graphs. AIP Conference Proceedings, 2215 (1) (2020), 070010.
• [10] M. Nabila, E.T. Baskoro, and H. Assiyatun, Ramsey graphs for a star on three vertices versus a cycle. In International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC): Atlantis Press, (2022), 5–10.