On Ramsey (C4 , K1,n)-minimal graphs

Hilda Assiyatun^∗a,c, Maya Nabila^b , Edy Tri Baskoroa,c

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

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

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

Let F, G and H be any simple graphs. The notation F → (G, H) means 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. If F → (G, H), then graph F is called a Ramsey graph for (G, H). Additionally, if the graph F satisfies that F − e ↛ (G, H) for any edge e of F, then graph F is called a Ramsey (G, H)-minimal. The set of all Ramsey (G, H)-minimal graphs is denoted by R(G, H). In this paper, we construct a new class of Ramsey (C4, K1,n)-minimal graphs.

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

DOI: 10.5614/ejgta.2023.11.1.12

1. Introduction

In this paper, all graphs are simple graphs. A cycle and a star of order n is denoted by Cⁿ and K1,n−1, respectively. 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: 20 December 2022, Revised: 20 March 2023, Accepted: 26 March 2023.

^cCenter for Research Collaboration on 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 these conditions:

• (i) F → (G, H), and
• (ii) F − e ↛ (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 on the Ramsey minimal graphs was initiated by Burr et al. [1]. In general, finding the Ramsey (G, H)-minimal graph is both a challenging and interesting problem to be solved. There are several papers that are dedicated to some Ramsey classes for specific graphs G and H. For instance, Burr et al. [2] showed that for an arbitrary graph G, the pair (mK2, G) is Ramsey-finite. In 1980, Burr et al. [3] proved that if H = K1,n and G is any 2-connected graph, then the set R(G, H) is infinite. Neset ˇ ˇril and Rodl [4] proved that if both ¨ G and H are 3-connected or if G and H are forests and neither of which is a union of stars, then the pair (G, H) is Ramseyinfinite. Over decades later, Borowiecki et al. [5] characterized all graphs in R(K3, K1,2). Mushi and Baskoro [6] gave necessary and sufficient conditions for all members of R(3K2, K1,n) for n ≥ 3. Additionally, for 3 ≤ n ≤ 7 they were able to list all Ramsey (3K2, K1,n)-minimal graphs of order at most 10 vertices.

Here are some of the latest related papers that discuss the pair of a cycle and a star. Nisa et al. [7] constructed some graphs in R(C6, K1,2). Nabila and Baskoro [8] gave some Ramsey (K1,2, Cn)-minimal graphs for n ∈ {5, 6, 8} and constructed the Ramsey (Cn, K1,2) graphs for n ∈ {10, 12, 14, 16, 18}. Hadiputra and Silaban [9] showed a new class of graphs using C4-paths and some edge additions are the members of an infinite family in R(K1,2, C4). Moreover, Nabila et al. [10] gave some finite and infinite classes of Ramsey (C4, K1,n)-minimal graphs for any n ≥ 3 in the form of path graphs.

In this paper, we give a new class of graph called theta-trees, which are constructed using an edge-weighted tree.

2. Main Results

In this section, we derive some sufficient conditions of Ramsey (G, H)-minimal graphs for G is a cycle C⁴ on four vertices and H is a star K1,n with n ≥ 2. Based on these sufficient conditions, we give some classes of Ramsey (C4, K1,n)-minimal graphs.

For any edge-weighted tree T on m edges, define a theta-tree graph θ[T] as follows.

Definition 2.1. Let T be an edge-weighted tree on m edges e1, e2, . . . , e^m with aⁱ ∈ N is the weight of eⁱ for each i. The theta-tree graph based on T, denoted by θ[T], is a graph constructed from T by replacing each edge eⁱ = (xⁱ , yi) by a union of aⁱ paths of length 2 whose internal vertices are disjoint. This internally disjoint union of aⁱ paths connects xⁱ and yⁱ .

From the Definition 2.1, we have V (θ[T]) = V (T) ∪ A¹ ∪ A² ∪ · · · ∪ Am, where Aⁱ = {ui,j | i ∈ [1, m], j ∈ [1, aⁱ ]}. All members of each Aⁱ are called internal vertices in θ[T] graph. For example, in Figure 1 we give the theta-tree graph θ[T] obtained from a tree T on 6 edges.

Figure 1. An edge-weighted tree T on 6 edges and the corresponding graph \(\theta[T]\).

2.1. Sufficient conditions

In this section, we present some sufficient conditions for an edge-weighted tree T on m edges such that the theta-tree graph \(\theta[T]\) is a Ramsey \((C_4, K_{1,n})\)-minimal graph.

Let T be an edge-weighted tree with m edges \(e_1, e_2, \ldots, e_m\) and \(a_i\) is the weight of \(e_i\) for each i. The sum of graph T, denoted by sum(T), is defined as the sum of all edge weights, namely \(\text{sum}(T) = \sum_{i=1}^m a_i\).

Theorem 2.1. Let n, m be natural numbers and T be a weighted tree on m edges \(e_1, e_2, \ldots, e_m\) with weights \(a_1, a_2, \ldots, a_m\), respectively, where \(n, m \geq 1\) and \(2 \leq a_i \leq 2n\). If the following statements hold

• (a) sum(T) = (m+1)n,
• (b) sum(T') < (l+1)n for each proper subtree T' of T induced by any l edges,

then \(\theta[T]\) is a Ramsey \((C_4, K_{1,n})\)-minimal graph.

Proof. Let T be a weighted tree on m edges \(e_1, e_2, \ldots, e_m\). Let \(G \cong \theta[T]\). Let \(\sum_{i=1}^m a_i = (m+1)n\), we will show that \(G \to (C_4, K_{1,n})\). Consider any red-blue coloring \(\alpha\) on the edges of G containing no blue copy of \(K_{1,n}\). Let B be the set of all blue edges in G by the coloring \(\alpha\). Since there is no blue copy of \(K_{1,n}\) in G, then

\[|B| \le (m+1)(n-1). \tag{1}\]

This is true since the maximum blue star is a \(K_{1,n-1}\), and it must have a center \(v_i\) for some \(i \in [1, m+1]\). Assume G has no red copy of \(C_4\) by \(\alpha\) coloring, then the number of blue edges incident with \(A_i\) is at least \(a_i - 1\) where at most one internal vertex in \(A_i\) is incident with two red edges, for each \(i \in [1, m]\). Thus,

\[|B| \ge \sum_{i=1}^{m} (a_i - 1) = -m + \sum_{i=1}^{m} a_i = (m+1)(n-1) + 1.\] (2)

From Eq. (1) and (2) we have a contradiction. It means that if G has no blue copy of K1,n, then G must contain a red copy of C4. Therefore, G → (C4, K1,n).

Next, we will show that G − e ↛ (C4, K1,n) for any edge e. Let e = ab ∈ G, where a is a non-internal vertex and b is an internal vertex in A^j for some j ∈ [1, m]. Define a red-blue coloring on the edges of G such that the edge incident to b is colored by red and the remaining edges are colored by red and blue with satisfying the following three conditions:

• (i) each internal vertex in Aⁱ is incident with at most one blue edge, such that the number of blue edges incident with Aⁱ is exactly aⁱ − 1 for each i ̸= j,
• (ii) each internal vertex in A^j is incident with at most one blue edge, such that the number of blue edges incident with A^j is exactly a^j − 2, and
• (iii) the number of blue edges incident to each non-internal vertex is exactly (n − 1).

This above coloring can always be done since from the conditions (i), (ii), (iii), and requirement (b), we obtain

\[|B| = a_j - 2 + \sum_{i=1 \text{ and } i \neq j}^m (a_i - 1) = (m+1)(n-1).\] (3)

where B is the set of all blue edges in G by the above coloring. By condition (iii) we have no blue K1,n in G. By conditions (i) and (ii) we have exactly one internal vertex incident with two red edges. Therefore, there is no red C⁴ in G. Thus, G is a Ramsey (C4, K1,n)-minimal graph. Note that the (b) condition is required; otherwise, the existence of a subtree T ′ of size l satisfying sum(T ′ ) = (l + 1)n would make G[T ′ ] → (C4, K1,n).

2.2. Special sequences of theta-tree graphs

From now on, let T be an edge-weighted tree on m edges e1, e2, . . . , e^m with the weights a1, a2, . . . , a^m and a¹ ≥ a² ≥ . . . ≥ am. In this section, we give some sequences a1, a2, . . . , a^m such that the theta-tree graph θ[T] is a Ramsey (C4, K1,n)-minimal graph.

Theorem 2.2. Let j ≥ 1 be fixed. If aⁱ = n + j for i ∈ [1, m] where n ≥ 2 with n = mj, then θ[T] is a Ramsey (C4, K1,n)-minimal graph.

Proof. Let T be an edge-weighted tree on m edges e1, e2, . . . , e^m with the weights aⁱ = n + j for each i ∈ [1, m]. In order to show that θ[T] is a Ramsey(C4, K1,n)-minimal graph, it is enough to prove that T satisfies the two conditions of Theorem 2.1. The first condition of Theorem 2.1 is satisfied, since sum(T) = (n + j) + · · · + (n + j) = (m + 1)n.

Now, consider any proper subtree T ′ of T induced by any l edges. Then, we have that sum(T ′ ) = l(n+j). It is easy to verify that, in any case, sum(T ′ ) < (l+ 1)n if 1 ≤ l ≤ m−1. So, the second condition of Theorem 2.1 is satisfied. Therefore, θ[T] is a Ramsey (C4, K1,n)-minimal graph.

Theorem 2.3. If a¹ = 2n − m + 1 and aⁱ = n + 1 for i ∈ [2, m] where n ≥ 2 and 2 ≤ m ≤ n, then θ[T] is a Ramsey (C4, K1,n)-minimal graph.

Proof. Let T be an edge-weighted tree on m edges \(e_1, e_2, \ldots, e_m\) where \(2 \leq m \leq n\). Let \(a_i\) be the weight of \(e_i\) with \(a_1 = 2n - m + 1\) and \(a_i = n + 1\) for each \(i \in [2, m]\). In order to show that \(\theta[T]\) is a Ramsey\((C_4, K_{1,n})\)-minimal graph, it is enough to prove that T satisfies the two conditions of Theorem 2.1. The first condition of Theorem 2.1 is satisfied, since sum\((T) = (2n - m + 1) + (n + 1) + \ldots + (n + 1) = (m + 1)n\).

Now, consider any proper subtree T' of T induced by any l edges. Then, we have that \(\operatorname{sum}(T') = l(n+1)\) or \(\operatorname{sum}(T') = (2n-m+1)+(l-1)(n+1)\). It is easy to verify that, in any case, \(\operatorname{sum}(T') < (l+1)n\) if \(2 \le m \le n\). So, the second condition of Theorem 2.1 is satisfied. Therefore, \(\theta[T]\) is a Ramsey \((C_4, K_{1,n})\)-minimal graph. \(\square\)

Theorem 2.4. If one of the following statements:

• (i) \(a_1 = 2n m k + 1, a_2 = n + k + 1, a_i = n + 1\) for \(i \in [3, m]\) where \(n \ge 6\), \(3 \le m \le n 2k 2\), and \(1 \le k \le \frac{n m}{2} 1\),
• (ii) \(a_1 = 2n m k, a_2 = n + k_1 + 1, a_3 = n + k_2 + 2, a_i = n + 1 \text{ for } i \in [4, m] \text{ where } n \ge 6,\)\(4 \le m \le n - 2k - 3, k_1 > k_2, k = k_1 + k_2, \text{ and } 1 \le k \le \frac{n - m - 1}{2} - 1,\)

holds, then \(\theta[T]\) is a Ramsey \((C_4, K_{1,n})\)-minimal graph.

Proof. Let T be an edge-weighted tree on m edges \(e_1, e_2, \ldots, e_m\). In order to show that \(\theta[T]\) is a Ramsey\((C_4, K_{1,n})\)-minimal graph, it is enough to prove that T satisfies the two conditions of Theorem 2.2. If (i) holds, then \(\operatorname{sum}(T) = (2n-m-k+1)+(n+k+1)+(n+1)+\ldots+(n+1) = (m+1)n\). Thus, the first condition of Theorem 2.1 is satisfied. Now, consider any proper subtree T' of T induced by any l edges. Then \(\operatorname{sum}(T') \leq (l-2)(n+1)+(n+k+1)+(2n-m-k+1)\). The upper bound is achieved if the edges \(e_1\) and \(e_2\) are in T'. It is easy to verify that \(\operatorname{sum}(T') < (l+1)n\) if \(3 \leq m \leq n-2k-2\). So, the second condition of Theorem 2.1 is satisfied.

If (ii) holds, then sum\((T)=(2n-m-k)+(n+k_1+1)+(n+k_2+2)+(n+1)\ldots+(n+1)=(m+1)n\). Thus, the first condition of Theorem 2.1 is satisfied. Now, consider any proper subtree T' of T induced by any l edges. Then sum\((T') \leq (l-3)(n+1)+(n+k_2+2)+(n+k_1+1)+(2n-m-k)\). The upper bound is achieved if the edges \(e_1\), \(e_2\), and \(e_3\) are in T'. It is easy to verify that sum(T') < (l+1)n if \(1 \leq m \leq n-2k-3\). So, the second condition of Theorem 2.1 is satisfied. Therefore, \(1 \leq n \leq n-2k-3\).

Theorem 2.5. If \(a_1 = 2n - \frac{1}{2}(m-1)m\) and \(a_i = n + m - (i-1)\) for \(i \in [2, m]\) where \(n \ge 6\) and \(2 \le m \le \left| \frac{-1 + \sqrt{1 + 8n}}{2} \right|\), then \(\theta[T]\) is a Ramsey \((C_4, K_{1,n})\)-minimal graph.

Proof. Let T be an edge-weighted tree on m edges \(e_1, e_2, \ldots, e_m\) with the weights \(a_1 = 2n - \frac{1}{2}(m-1)m\) and \(a_i = n + m - (i-1)\) for each \(i \in [2, m]\). In order to show that \(\theta[T]\) is a Ramsey \((C_4, K_{1,n})\)-minimal graph, it is enough to prove that T satisfies the two conditions of Theorem 2.1. The first condition of Theorem 2.1 is satisfied, since \(\operatorname{sum}(T) = (2n - \frac{1}{2}(m-1)m) + (n+m-1) + \cdots + (n+1) = (m+1)n\).

Now, consider any proper subtree T' of T induced by any l edges. Then, we have that \(\operatorname{sum}(T') \leq (2n - \frac{1}{2}(m-1)m) + \cdots + (n+2) = mn-1\). It is easy to verify that, in any case, \(\operatorname{sum}(T') < (l+1)n\) if \(1 \leq l \leq m-1\). So, the second condition of Theorem 2.1 is satisfied. Therefore, \(\theta[T]\) is a Ramsey \((C_4, K_{1,n})\)-minimal graph.

Acknowledgment

This research has been supported by the PPMI program, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung and by the Research grant of "Pendidikan Magister menuju Doktor untuk Sarjana Unggulan (PMDSU)", Ministry of Education, Culture, Research and Technology, Indonesia.

References

• [1] S.A. Burr, P. Erdos and L. Lov ˝ asz, On graphs of Ramsey type, ´ Ars Combin. 1 (1976), 167–190.
• [2] S.A. Burr, P. Erdos, 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. Erdos, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, Ramsey minimal graphs ˝ for the pair star-connected graph, Studia Sci. Math. Hungar. 15 (1980), 265–273.
• [4] J. Neset ˇ ˇril and V. Rodl, The structure of critical Ramsey graphs, ˝ Acta Mathematica Hungarica 32(3-4) (1978), 295–300.
• [5] M. Borowiecki, I. Schiermeyer and E. Sidorowicz, Ramsey (K1,2, K3)-minimal Graphs, Electron. J. Combin. 12 (2005), #R20.
• [6] H. Muhshi and E.T. Baskoro, Matching-star Ramsey minimal graphs, Mathematics in Computer Science 9(4) (2015), 443–452.
• [7] F. Nisa, D. Rahmadani, Purwanto, and H. Susanto, On Ramsey (P3, C6)-minimal graphs, AIP Conference Proceedings 2215(1) (2020), 070010.
• [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.F. Hadiputra and D.R. Silaban, Infinite Family of Ramsey (K1,2, C4)-minimal Graphs, Journal of Physics: Conference Series 1722(1) (2020), 012049.
• [10] M. Nabila, H. Assiyatun and E.T. Baskoro, Ramsey minimal graphs for a pair of a cycle on four vertices and an arbitrary star, Electron. J. Graph Theory Appl. 10(1) (2022), 289–299.