The connected size Ramsey number for matchings versus small disconnected graphs

Hilda Assiyatun, Budi Rahadjeng, Edy Tri Baskoro

Abstract


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 (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 c(G, H). We will derive an upper bound of c(nK2, H), n ≥ 2 where H is 2Pm or 2K1, t,  and find the exact values of c(nK2, H),  for some fixed n.


Keywords


connected size Ramsey number, disconnected graph, matching

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.1.9

Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats