Authors: E.T. Baskoro, D.R. Silaban, S. Uttunggadewa Title: On the restricted size Ramsey number involving path P_{3} Source: Discussiones Mathematicae Graph Theory Received 12.01.2018, Revised 11.10.2018, Accepted 11.10.2018, doi: 10.7151/dmgt.2188 | |
Abstract: For any pair of graphs G and H, both the size Ramsey number \hat{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, \hat{r}(G,H)\le 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 \hat{r}(G,H) attains the upper bound? and (2) Do there exist graphs G and H such that \hat{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=P_{3} and H is a connected graph. | |
Keywords: restricted size Ramsey number, path, connected graph, star | |
Links: |