On the restricted size Ramsey number involving a path P_3
Author(s) -
Edy Tri Baskoro,
Denny Riama Silaban,
Saladin Uttunggadewa
Publication year - 2018
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2188
Subject(s) - ramsey's theorem , combinatorics , mathematics , bounded function , graph , upper and lower bounds , ramsey theory , discrete mathematics , bound graph , graph power , line graph , mathematical analysis
For any pair of graphs G and H, both the size Ramsey number ̂r(G,H) and the restricted size Ramsey number r*(G,H) are bounded above by the size of the complete graph with order equals to the Ramsey number r(G,H), and bounded below by e(G) + e(H) − 1. Moreover, trivially, ̂r(G,H) ≤ r*(G,H). When introducing the size Ramsey number for graph, Erdős et al. (1978) asked two questions; (1) Do there exist graphs G and H such that ˆr(G,H) attains the upper bound? and (2) Do there exist graphs G and H such that ̂r(G,H) is significantly less than the upper bound? In this paper we consider the restricted size Ramsey number r*(G,H). We answer both questions above for r*(G,H) when G = P3 and H is a connected graph.
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