Connected Size Ramsey Numbers for Matchings versus Cycles or Paths
Author(s) -
Budi Rahadjeng,
Edy Tri Baskoro,
Hilda Assiyatun
Publication year - 2015
Publication title -
procedia computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.334
H-Index - 76
ISSN - 1877-0509
DOI - 10.1016/j.procs.2015.12.071
Subject(s) - computer science , ramsey's theorem , algorithm , mathematical optimization , theoretical computer science , mathematics , graph
Let F, G, and H be finite, simple and undirected graphs. The connected size Ramsey number r̂c(G, H) of graph G and H is the least integer k such that there is a connected graph F with k edges and if the edge set of F is arbitrarily colored by red or blue, then there always exists either a red copy of G or a blue copy of H. In this paper, we determine the connected size Ramsey number r̂c(2K2, Cn), for n ≥ 4, an upper bound of r̂c(nK2, P4), for n ≥ 2, and the exact value of r̂c(nK2, P4), for 2 ≤ n ≤ 5
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom