On the restricted size Ramsey number for P3 versus dense connected graphs

Denny Riama Silaban, Edy Tri Baskoro, Saladin Uttunggadewa

Abstract


Let F, G and H be simple graphs. A graph F is said a (G,H)-arrowing graph if in any red-blue coloring of edges of F we can find a red G or a blue H. The size Ramsey number of G and H, ŕ(G,H), is the minimum size of F. If the order of F equals to the Ramsey number of G and H, r(G,H), then the minimum size of F is called the restricted size Ramsey number of G and H, r*(G,H). The Ramsey number of G and H, r(G,H), is the minimum order of F. In this paper, we study the restricted size number involving a P3.  The value of r*(P3,Kn) has been given by Faudree and Sheehan. Here, we examine r*(P3,H) where H is dense connected graph.


Keywords


restricted size Ramsey number, size Ramsey number, dense connected graph, path

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2020.8.2.14

References

S.A. Burr, A survey of noncomplete Ramsey theory for graphs, Ann. New york Acad. Sci. 328 (1979), 58--75; doi:10.1111/j.1749-6632.1979.tb17768.x.

V. Chvatal and F. Harary, Generalized Ramsey theory for graphs III: small off-diagonal number, Pac. J. Math. 41 (2) (1972), 335--345; doi:10.2140/pjm.1972.41.335.

R. Diestel. Graph Theory, Springer-Verlag Heidelberg, New York, 4 edition, 2005.

P. Erdos, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, The size Ramsey number, Period. Math. Hung., Volume 9 (1978), Issue 1-2, 145--161.

R.J. Faudree and R. Schelp, A survey of results on the size Ramsey numbers, Paul Erdos and His Mathematics II 10 (2002), 291--309.

R.J. Faudree and J. Sheehan, Size Ramsey numbers for small-order graphs, J. Graph Theory 7 (1983), 53--55.

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.

F. Harary and Z. Miller, Generalized Ramsey theory VIII: the size Ramsey number of small graphs, Studies in Pure Mathetematics - To the Memory of Paul Turan, Birkhauser (1983), 271--283; doi:10.1007/978-3-0348-5438-2_25.

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

D. R. Silaban, E. T. Baskoro, and S. Uttunggadewa, On the restricted size Ramsey number, Procedia Comput. Sci. 74 (2015), 21--26; doi:10.1016/j.procs.2015.12.069.

D.R. Silaban, E.T. Baskoro, and S. Uttunggadewa, On the restricted size Ramsey number involving a path P3, Discus. Math. Graph T. Volume 39 (2019), Issue 2, 741--755; doi.org/10.7151/dmgt.2188.

D.R. Silaban, E.T. Baskoro, and S. Uttunggadewa, Restricted size Ramsey number for P3 versus small paths, AIP Conf. Proc.1707 (2016); doi:10.1063/1.4940821.

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), Issue 1, 155--162;

doi:10.5614/ejgta.2017.5.1.15.

D.R. Silaban, E.T. Baskoro, and S. Uttunggadewa, Restricted size Ramsey number for P3 versus dense connected graphs of order six, AIP Conf. Proc. 1862 (2017) 030136; doi: 10.1063/1.4991240.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats