Geodesic
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/

[1] H. Bielak, Remarks on the size Ramsey number of graphs, Period. Math. Hungar. 18 (1987) 27–38. doi:10.1007/BF01849031

[2] H. Bielak, Size Ramsey numbers for some regular graphs, Electron. Notes Discrete Math. 24 (2006) 39–45. doi:10.1016/j.endm.2006.06.007

[3] H. Bielak, Size Ramsey numbers for some regular graphs, Discrete Math. 309 (2009) 6446–6449. doi:10.1016/j.disc.2008.11.011

[4] S.A. Burr, A survey of noncomplete Ramsey theory for graphs, Ann. N.Y. Acad. Sci. 328 (1979) 58–75. doi:10.1111/j.1749-6632.1979.tb17768.x

[5] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs, III. Small off-diagonal numbers, Pacific J. Math. 41 (1972) 335–345. doi:10.2140/pjm.1972.41.335

[6] R. Diestel, Graph Theory, 4 Edition (Springer-Verlag Heidelberg, New York, 2005).

[7] A. Dudek, F. Khoeini and P. Pralat, Size-Ramsey numbers of cycles versus a path, Discrete Math. 341 (2018) 2095–2103. doi:10.1016/j.disc.2018.04.008

[8] A. Dudek and P. Pralat, An alternative proof of the linearity of the size-Ramsey number of paths, Combin. Probab. Comput. 24 (2015) 551–555. doi:10.1017/S096354831400056X

[9] P. Erdős, R.J. Faudree, C.C. Rousseau and R. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978) 145–161. doi:10.1007/BF02018930

[10] P. Erdős and R.J. Faudree, Size Ramsey function, in: Sets, graphs, and numbers, Colloq. Math. Soc. Janos Bolyai 60 (1991) 219–238.

[11] R.J. Faudree, C.C. Rousseau and J. Sheehan, A class of size Ramsey numbers involving stars, in: Graph Theory and Combinatorics - A Volume in Honor of Paul Erdős, B. Bollobás (Ed(s)), (Academic Press, London., 1984) 273–282.

[12] R.J. Faudree and R.H. Schelp, A survey of results on the size Ramsey number, in: Proc. of the Conference Paul Erdős and His Mathematics, Budapest 1999, Bolyai Soc. Math. Stud. 11 (2002) 291–309.

[13] R.J. Faudree and J. Sheehan, Size Ramsey numbers for small-order graphs, J. Graph Theory 7 (1983) 53–55. doi:10.1002/jgt.3190070107

[14] R.J. Faudree and J. Sheehan, Size Ramsey numbers involving stars, Discrete Math. 46 (1983) 151–157. doi:10.1016/0012-365X(83)90248-0

[15] F. Harary and Z. Miller, Generalized Ramsey theory VIII. The size Ramsey number of small graphs, Stud. Pure Math. (1983) 271–283. doi:10.1007/978-3-0348-5438-2_25

[16] R. Javadi, F. Khoeini, G. Omidi and A. Pokrovskiy, On the size-Ramsey number of cycles (2017). arXiv:1701.07348v1 [math.CO]

[17] S. Letzter, Path Ramsey number for random graphs, Combin. Probab. Comput. 25 (2016) 612–622. doi:10.1017/S0963548315000279

[18] R. Lortz and I. Mengersen, Size Ramsey results for paths versus stars, Australas. J. Combin. 18 (1998) 3–12.

[19] M. Miralaei, G.R. Omidi and M. Shahsiah, Size Ramsey numbers of stars versus cliques (2016). arXiv:1601.06599v1 [math.CO]

[20] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2017) #DS1.

[21] D.R. Silaban, E.T. Baskoro and S. Uttunggadewa, On the restricted size Ramsey number, Procedia Computer Science 74 (2015) 21–26. doi:10.1016/j.procs.2015.12.069

[22] D.R. Silaban, E.T. Baskoro and S. Uttunggadewa, Restricted size Ramsey number for P 3 versus small paths, AIP Conf. Proc. 1707 (2016) 020020. doi:10.1063/1.4940821

[23] D.R. Silaban, E.T. Baskoro and S. Uttunggadewa, Restricted size Ramsey number for path of order three versus graph of order five, Electron. J. Graph Theory Appl. 5 (2017) 155–162. doi:10.5614/ejgta.2017.5.1.15