The connected size Ramsey number for matchings versus small disconnected graphs
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 r̂(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 r̂c(G, H). We will derive an upper bound of r̂c(nK2, H), n ≥ 2 where H is 2Pm or 2K1, t, and find the exact values of r̂c(nK2, H), for some fixed n.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2019.7.1.9
References
S.A. Burr, P. Erdo ̋s, R.J. Faudree, C.C. Rousseau, R.H. Schelp, Ramsey minimal graphs for multiple copies, Nederl. Akad. wetensch, Proc. Ser. A81 (1978), 187–195.
P. Erdo ̋s, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), 145–161.
P. Erdo ̋s, R.J Faudree, Size Ramsey numbers involving matching, Colloquia Math. Societatis Ja ́nos Bolyai 37 (1981), 247–264.
R.J. Faudree, R.H. Schelp, A survey of results on the size Ramsey number, in Paul Erdo ̋s and his mathematics II (Budapest, 1999), Bolyai Soc. Math. Stud. 11 (2002), 291–309.
Bielak, H., Note size Ramsey number for some regular graphs, Discrete Math. 309 (2012), 6446–6449.
Ben-Eliezer, I., Krivelevich, M., Sudakov, B., The size Ramsey of a directed path, J. Combin. Theory 102 (2012), 743–755.
B. Rahadjeng, E.T. Baskoro, H. Assiyatun, Connected size Ramsey numbers for matchings vs small stars or cycles, Proc. Indian Acad. Sci. Math. Sci. 127 (5) (2017), 787–792.
B. Rahadjeng, E.T. Baskoro, H. Assiyatun, Connected size Ramsey numbers of matchings and stars, AIP Conf. Proc., 1707, 020015 (2016); doi :10.1063/1.4940816.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.<div class="statcounter"><a title="web analytics" href="http://statcounter.com/" target="_blank"><img class="statcounter" src="//c.statcounter.com/11284516/0/7b1b10eb/1/" alt="web analytics"></a></div>