Restricted size Ramsey number for P3 versus cycle

Joanna Cyman^a , Tomasz Dzido^b

joanna.cyman@pg.edu.pl, tdz@inf.ug.edu.pl

Let F, G and H be simple graphs. We say F → (G, H) if for every red-blue coloring of the edges of F there exists a red copy of G or a blue copy of H in F. The Ramsey number r(G, H) is defined as r(G, H) = min{|V (F)| : F → (G, H)}, while the restricted size Ramsey number r ∗ (G, H) is defined as r ∗ (G, H) = min{|E(F)| : F → (G, H), |V (F)| = r(G, H)}. In this paper we determine previously unknown restricted size Ramsey numbers r ∗ (P3, Cn) for 7 ≤ n ≤ 12. We also give new upper bound r ∗ (P3, Cn) ≤ 2n − 2 for even n ≥ 10.

Keywords: size Ramsey number, restricted, path, cycle. Mathematics Subject Classification: 05C55, 05D10

DOI: 10.5614/ejgta.2020.8.2.12

1. Introduction

Paul Erdos had a tremendous impact on many areas of mathematics, one of these areas is Ramsey ˝ theory. His contributions started with the classical Ramsey numbers r(G, H). In 1978, Erdos˝ et al. in [3] defined the size Ramsey number rˆ(G, H) as the smallest size of a graph F such that, under any red-blue coloring of its edges, the graph F contains a red copy of G or a blue copy of H. In [6] one can find a survey of results along with the influence of Paul Erdos on the development of ˝ size Ramsey theory.

The restricted size Ramsey number r ∗ (G, H) is a problem connecting Ramsey number and size Ramsey number. For the restricted size Ramsey number, if r is the Ramsey number of G and

Received: 2 April 2019, Revised: 19 June 2020, Accepted: 2 August 2020.

^aGdansk University of Technology, Department of Technical Physics and Applied Mathematics, Narutowicza 11/12, 80-952 Gda ´ nsk, Poland ´ b Institute of Informatics, University of Gdansk, Wita Stwosza 57, 80-952 Gda ´ nsk, Poland ´

H then F must be a spanning subgraph of K^r with the smallest size such that for any red-blue coloring of edges of F we have a red copy of G or a blue copy of H in F. Therefore, the size of K^r is the upper bound for the restricted size Ramsey number of G and H and the restricted size Ramsey number must be greater or equal to the size Ramsey number for a given pair of graphs. In addition, we have r˜(G, H) ≤ rˆ(G, H), where r˜(G, H) is the on-line Ramsey number (the definition and properties of these numbers can be found in [2]). If both G and H are complete graphs then F = K^r (see [3]). The case of complete graph is one of a few cases for which that upper bound is reached. In general, the more sparse both graphs G and H are, the problem of finding the restricted size Ramsey number for those pair of graphs is harder. Only two results for the exact value of restricted size Ramsey number involving a class of graph known so far, that are, for K1,k versus Kⁿ ([7]) and G versus K1,k, where G is K3, K⁴ − e, or C⁵ ([4]). For other few classes of graphs, the problem is solved partially.

Some results for size Ramsey number was presented by Faudree and Schelp in 2002 ([6]). It had shown that r ∗ (P3, C3) = 8, r ∗ (P3, C4) = 6, r ∗ (P3, C5) = 9. In 2015, Silaban et al. proved the last known exact value, namely r ∗ (P3, C6) = 9 [9]. In addition, they give lower and upper bound for r ∗ (P3, Cn), where n ≥ 8 is even (see Theorem 3 below). In this paper, we determine previously unknown restricted size Ramsey numbers, namely r ∗ (P3, Cn) for 7 ≤ n ≤ 12, and we improve the upper bound for r ∗ (P3, Cn), that is we prove that r ∗ (P3, Cn) ≤ 2n − 2 for even n ≥ 10.

In general, we follow graph theory terminology and notation of [9].

2. Known results

In this section, we list a few known definitions and theorems that we will need in proving our results.

The Turan number ´ ex(n, G) is the maximum number of edges in any n-vertex graph which does not contain a subgraph isomorphic to G. A graph on n vertices is said to be extremal with respect to G if it does not contain a subgraph isomorphic to G and has exactly ex(n, G) edges.

In 1989, Clapham et al. [1] determined all values of ex(n, C4) for n ≤ 21. They also characterized all the corresponding extremal graphs. In Theorem 1 we quote value for ex(7, C4) and we show (Figure 1) five corresponding extremal graphs. We will use this in the proof of Theorem 5.

Theorem 1 ([1]).

\[ex(7, C_4) = 9\]

and there are 5 extremal graphs for this number illustrated in Figure 1.

In our work we will also use a well known the Ramsey number for paths and cycles that was calculated by Faudree et al. in [5].

Theorem 2 ([5]). For all integers n ≥ 4,

\[r(P_3, C_n) = n.\]

Figure 1. All extremal graphs for \(ex(7, C_4)\).

In 2015, Silaban et al. [9] proved the lower and the upper bound for the restricted size Ramsey number for \(P_3\) and cycles. At the end of our article we improve the upper bound for this number.

Theorem 3 ([9]). For even \(n \geq 8\),

\[\frac{3}{2}n + 2 \le r^*(P_3, C_n) \le 2n - 1.\]

3. New results

In order to find the value of \(r^*(P_3, C_n)\), we find a graph F with the smallest possible size such that \(F \to (P_3, C_n)\). According to Theorem 2 the graph F must have n vertices.

3.1. Determining the value of \(r^*(P_3, C_7)\)

First, we give the following condition for graph F satisfying \(F \to (P_3, C_7)\).

Lemma 4. Let F be a graph with |V(F)| = 7 and \(C_4 \subseteq \overline{F}\), then \(F \nrightarrow (P_3, C_7)\).

Proof. Suppose there is F with |V(F)|=7 such that \(\overline{F}\) contains cycle \(C_4\), say \(v_1,v_2,v_3,v_4,v_1\). By coloring possible edges \(v_1v_3,\,v_2v_4\in E(F)\) by red and the remaining edges of F by blue, we obtain a 2-coloring of F which contains neither a red \(P_3\) nor a blue \(C_7\).

Theorem 5. \(r^*(P_3, C_7) = 13\).

Proof. First, we will prove that \(r^*(P_3, C_7) \geq 13\). From Lemma 4 and Theorem 1 we imply that \(r^*(P_3, C_7) \geq 12\). Suppose that \(r^*(P_3, C_7) = 12\). Let F be a graph on 7 vertices and 12 edges. By Lemma 4, if \(F \to (P_3, C_7)\), then \(C_4 \not\subseteq \overline{F}\) and therefore \(\overline{F}\) is one of the five graphs \(G_i\), \(1 \leq i \leq 5\) from Figure 1. Furthermore, since \(\Delta(G_i) \geq 4\) for \(i \in \{1, 2, 3\}\), and by coloring \(u_2u_7\), \(u_3u_5\), \(v_1v_6\), \(v_3v_7\), \(v_4v_5\) in red (see Figure 2) we obtain, for all \(\overline{G_i}\), a 2-coloring of edges which contains neither a red \(P_3\) nor a blue \(C_7\). In fact, if \(\Delta(G_i) \geq 4\), then there is a vertex of degree at most 2 in \(\overline{G_i}\). To avoid a blue \(C_7\) we color in red one edge coming out of this vertex (if any). Hence, \(F \nrightarrow (P_3, C_7)\) and consequently we have \(r^*(P_3, C_7) \geq 13\).

Figure 2. Two extremal graphs G⁴ and G⁵ for ex(7, C4).

Figure 3. The complement of the graph F7.

Next, we will show that r ∗ (P3, C7) ≤ 13. Let F⁷ be the complement of the graph shown in Figure 3. To prove that F⁷ → (P3, C7), let χ be any red-blue coloring of edges of F⁷ such that there is no red P³ in F7. We will show that the coloring χ will imply a blue C⁷ in F7. To do so, consider vertex v4. There are 4 edges incidence to this vertex, at most one of them can be colored by red. Up to the symmetry of F7, without loss of generality, we can assume that v1v⁴ is red or all edges viv4, i ∈ {1, 3, 6, 7} are blue. Nonexistence a red P³ forces the red edges to be a matching and that it suffices to consider maximum matchings. Then, using symmetries, there are only five subcases to discuss.

• 1. Edge v1v⁴ is red.
  • 1.1 if v2v⁵ and v3v⁶ is red, then v1, v5, v3, v4, v6, v2, v7, v¹ is the blue cycle,
  • 1.2 if v2v⁶ and v3v⁵ are red, then v1, v5, v2, v7, v4, v3, v6, v¹ is the blue cycle,
  • 1.3 if v2v⁶ and v3v⁷ are red, then the cycle v1, v6, v4, v3, v5, v2, v7, v¹ is blue.
• 2. All edges viv4, i ∈ {1, 3, 6, 7} are blue. Then we have two subcases:
  • 2.1 if v2v5, v1v6, v3v⁷ are red, then we obtain the following blue cycle: v1, v5, v3, v4, v6, v2, v7, v1,
  • 2.2 if v2v6, v1v5, v3v⁷ are red, then the cycle: v1, v4, v6, v3, v5, v2, v7, v¹ is blue.

For all cases, there is always a blue C7, so F⁷ → (P3, C7) and the proof is complete.

3.2. Upper bounds for r ∗ (P3, Cn)

In [9] Silaban et al. proved that r ∗ (P3, Cn) ≤ 2n − 1. In this section we will show that this upper bound can be improved and we prove the following theorem.

Theorem 6. For even n ≥ 12,

\[r^*(P_3, C_n) \le 2n - 2.\]

Figure 4. The graph Fⁿ → (P3, Cn) for n ≥ 12 and even n, t = n−2 2 .

Proof. Let t = n−2 2 and let Fⁿ be a graph with

\[V(F_n) = \{x, y\} \cup \{u_i, v_i | i = 1, \dots, t\}\]

and

\[E(F_n) = \{xu_1, xv_1, xu_3, u_ty, v_ty, v_{t-2}y\} \cup S,\]

where

\[S = \{u_i u_{i+1}, v_i v_{i+1}, v_i u_{i+1}, u_i v_{i+1} | i = 1, \dots, t-1\}\]

(see Fig. 4). In order to prove that Fⁿ → (P3, Cn), let χ be any red-blue coloring of edges of Fⁿ such that there is no red P³ in Fn. We will show that the coloring Fⁿ will imply a blue Cⁿ in Fn.

FACT 1. Observe that if we have any two independent blue paths to uⁱ and vⁱ , then we can extend these paths step by step to vertices u^j and to v^j for 1 ≤ i < j ≤ t. To do so, let us consider the vertex uⁱ . Since under the coloring χ there is no red P3, at most one of edges {uiui+1, uivi+1} can be red. If uiui+1 is red, then {uivi+1, viui+1} must be blue. Using these 2 blue edges, we can extend our blue paths to ui+1 and vi+1, independently. If uivi+1 is red, then {uiui+1, vivi+1} must be blue. Using these 2 blue edges, we also can extend our blue paths to ui+1 and vi+1, independently. We can do the same process to extend our blue paths until reaching u^j and v^j .

FACT 2. There are always two independent blue paths from x to uⁱ and from x to vⁱ for i = 1 or i = 3. To prove this fact, let us consider the the vertex x. There are 3 incident edges to this vertex, at most one of them can be colored by red. Up to the symmetry of Fn, we can assume that at most one edge of set {xu1, xu3} is red.

If \(xu_3\) is red, then \(xu_1\) and \(xv_1\) must be blue, therefore we have two blue paths from x to \(u_1\) and from x to \(v_1\). Note that a similar situation occurs if none of edges incidence to x is red.

Now we can assume that \(xu_1\) is red. In this case \(xv_1\) and \(xv_3\) are blue so we have one path from x to \(u_3\). We will construct a path of size 6 with the set \(\{u_1,u_2,v_1,v_2\}\)) as inner vertices, namely the path from x to \(v_3\). To do this consider the vertex \(u_2\). Under the coloring \(\chi\), at most one of edges \(\{u_2u_3,u_2v_3,u_2v_1\}\) can be red. In all cases we obtain one among two possible blue paths from x to \(v_3\), namely \(xv_1u_2u_1v_2v_3\) or \(xv_1v_2u_1u_2v_3\).

Similarly, using the symmetry of \(F_n\), we get two independent blue paths from y to \(u_j\) and from y to \(v_j\) for j = t or j = t - 2.

By using Fact 1 and 2, we obtain a blue cycle \(C_n\) in F. Observe that the theorem holds for \(3 \le t - 2\) and \(n \ge 12\).

Silaban et al. ([9]) gave the upper bound for the restricted size Ramsey number of \(P_3\) versus \(P_n\). They proved that for even n > 8, \(r^*(P_3, P_n) \le 2n - 1\). From the proof of Theorem 6 we see that if we delete edge \(xu_3\) then for any 2-coloring of edges of \(F_n \setminus \{xu_3\}\) that avoid red \(P_3\), it must imply a blue \(P_n\) in \(F_n\). It means we get a better upper bound of the restricted size Ramsey number for \(P_3\) versus \(P_n\), even \(n \ge 12\), as given in the following corollary.

Corollary 7. For \(n \ge 12\) and even n, \(r^*(P_3, P_n) \le 2n - 3\).

3.3. Computational Approach

In this subsection we use a computational approach to determine the exact values of \(r^*(P_3, C_n)\), \(8 \le n \le 12\). We use the following Algorithm 1 to find such numbers.

Algorithm 1 Deciding whether graph \(F \to (P_3, \overline{C_n})\) or not

Require: Adjacency matrix of biconnected graph F on n vertices.
    Ensure: F \to (P_3, C_n) or F \nrightarrow (P_3, C_n).
 1: for m = \lfloor \frac{n}{2} \rfloor \to 0 do
        for every subset S of m edges that compose independent edge set do
2:
            F' = F - S
3:
            find a Hamiltonian cycle in F'
4:
            if no Hamiltonian cycle in F' then return F \rightarrow (P_3, C_n), Break.
 5:
            end if
6:
        end for
7:
        m := m - 1
 9: end for
10: return F \rightarrow (P_3, C_n)

We generate all the adjacency matrices of biconnected graphs with n vertices (\(8 \le n \le 12\)) with minimum degree 3 by using a program called geng [8]. In order to find Hamiltonian cycle, algorithm uses recursive depth-first search. Note that the starting point should not matter as the cycle can be started from any point.

Table 1: Restricted size Ramsey numbers \(r^*(P_3, C_n)\), \(8 \le n \le 12\).

From the above algorithm, we obtain the results which are presented in Table 1. This table provides the value of \(r^*(P_3, C_n)\) and the number of non-isomorphic graphs F of order n and size \(r^*(P_3, C_n)\) such that \(F \to (P_3, C_n)\). Based on computer calculations, it turned out that in fact it was enough to consider cases where \(m \in \{\lfloor \frac{n}{2} \rfloor, \lfloor \frac{n}{2} \rfloor - 1, \lfloor \frac{n}{2} \rfloor - 2\}\).

Examples of resulting graphs are presented in Fig. 5, 6, 7 and 4. For the number \(r^*(P_3, C_8)\) an example is a graph \(K_{4,4} - e\).

Figure 5. Complement of the graph \(F_9 \rightarrow (P_3, C_9)\).

Figure 6. Graph \(F_{10} \to (P_3, C_{10})\).

4. Conclusion

In this paper we established six new restricted size Ramsey numbers \(r^*(P_3, C_n)\) for \(7 \le n \le 12\). In addition, we gave the new upper bound for \(n \ge 10\) and even n. It follows that the first open case of \(r^*(P_3, C_n)\) is now \(r^*(P_3, C_{13})\) and is certainly worth of further investigation. Based on results known earlier and described in this work as well as computer experiments for some bipartite graphs that are not presented here, let us formulate the following conjecture.

Conjecture 8. For all \(n \ge 10\), we have

\[r^*(P_3, C_n) = 2n - 2.\]

Figure 7. Graph F¹¹ → (P3, C11).

Acknowledgment

We would like to thank the student of the University of Gdansk Maciej Godek for the inde- ´ pendent performance of some computer experiments that confirmed the correctness of the results contained in the article.

References

• [1] C.R.J. Clapham, A. Flockhart, J. Sheehan, Graphs without four-cycles, Journal of Graph Theory, 13 (1989) 29–47.
• [2] J. Cyman, T. Dzido, J. Lapinskas, A. Lo, On-line Ramsey Numbers of Paths and Cycles, Electronic Journal of Combinatorics, 22 (2015) #P1.15
• [3] P. Erdos, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, ˝ Periodica Mathematica Hungarica 9(1-2) (1978) 145–161.
• [4] P. Erdos, R.J. Faudree, Size Ramsey functions, in: Sets, graphs, and numbers. ˝ Colloq. Math. Soc. Janos Bolyai 60 (eds. G. Halasz et al.) North-Holland Publishing Co. Amsterdam 1992, 219–238.
• [5] R.J. Faudree, S.L. Lawrence, T.D. Parsons, R.H. Schelp, Path-Cycle Ramsey Numbers, Discrete Mathematics 10 (1974) 269–277.
• [6] R.J. Faudree, R.H. Schelp, A survey of results on the size Ramsey number Paul Erdos and ˝ his mathematics II (2002) 291–309.
• [7] R.J. Faudree, J. Sheehan, Size Ramsey numbers involving stars, Discrete Mathematics 46 (1983) 151–157.
• [8] B.D. McKay, A. Piperno, Nauty and traces user's guide (version 2.6), http://cs.anu.edu.au/ bdm/nauty/nug26.pdf
• [9] D.R. Silaban, E.T. Baskoro, S. Uttunggadewa, On the restricted size Ramsey number, Procedia Computer Science 74 (2015) 21–26.