On the Restricted Size Ramsey Number Involving a Path P3
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 757-769
Voir la notice de l'article provenant de la source Library of Science
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 = P_3 and H is a connected graph.
Keywords:
restricted size Ramsey number, path, connected graph, star
@article{DMGT_2019_39_3_a10,
author = {Silaban, Denny Riama and Baskoro, Edy Tri and Uttunggadewa, Saladin},
title = {On the {Restricted} {Size} {Ramsey} {Number} {Involving} a {Path} {P\protect\textsubscript{3}}},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {757--769},
publisher = {mathdoc},
volume = {39},
number = {3},
year = {2019},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a10/}
}
TY - JOUR AU - Silaban, Denny Riama AU - Baskoro, Edy Tri AU - Uttunggadewa, Saladin TI - On the Restricted Size Ramsey Number Involving a Path P3 JO - Discussiones Mathematicae. Graph Theory PY - 2019 SP - 757 EP - 769 VL - 39 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a10/ LA - en ID - DMGT_2019_39_3_a10 ER -
%0 Journal Article %A Silaban, Denny Riama %A Baskoro, Edy Tri %A Uttunggadewa, Saladin %T On the Restricted Size Ramsey Number Involving a Path P3 %J Discussiones Mathematicae. Graph Theory %D 2019 %P 757-769 %V 39 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a10/ %G en %F DMGT_2019_39_3_a10
Silaban, Denny Riama; Baskoro, Edy Tri; Uttunggadewa, Saladin. On the Restricted Size Ramsey Number Involving a Path P3. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 757-769. http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a10/