A proof of a conjecture on matching-path connected size Ramsey number

Yixin Zhang; Yanbo Zhang; Hexuan Zhi; Yixin Zhang; Yanbo Zhang; Hexuan Zhi

doi:10.3934/math.2023406

AIMS Mathematics

2023, Volume 8, Issue 4: 8027-8033. doi: 10.3934/math.2023406

Previous Article Next Article

Research article

A proof of a conjecture on matching-path connected size Ramsey number

1.
School of Mathematical Sciences, Hebei Normal University, Shijiazhuang 050024, China
2.
Hebei International Joint Research Center for Mathematics and Interdisciplinary Science, Shijiazhuang 050024, China

Received: 25 October 2022 Revised: 18 January 2023 Accepted: 19 January 2023 Published: 31 January 2023
MSC : 05C55, 05D10

For two graphs $ G_1 $ and $ G_2 $, the connected size Ramsey number $ {\hat{r}}_c(G_1, G_2) $ is the smallest number of edges of a connected graph $ G $ such that if each edge of $ G $ is colored red or blue, then $ G $ contains either a red copy of $ G_1 $ or a blue copy of $ G_2 $. Let $ nK_2 $ be a matching with $ n $ edges and $ P_4 $ a path with four vertices. Rahadjeng, Baskoro, and Assiyatun [Procedia Comput. Sci. 74 (2015), 32-37] conjectured that $ \hat{r}_{c}(nK_2, P_4) = 3n-1 $ if $ n $ is even, and $ \hat{r}_{c}(nK_2, P_4) = 3n $ otherwise. We verify the conjecture in this short paper.
- size Ramsey number,
- connected size Ramsey number,
- matching,
- path
Citation: Yixin Zhang, Yanbo Zhang, Hexuan Zhi. A proof of a conjecture on matching-path connected size Ramsey number[J]. AIMS Mathematics, 2023, 8(4): 8027-8033. doi: 10.3934/math.2023406

Related Papers:

Abstract

For two graphs $ G_1 $ and $ G_2 $, the connected size Ramsey number $ {\hat{r}}_c(G_1, G_2) $ is the smallest number of edges of a connected graph $ G $ such that if each edge of $ G $ is colored red or blue, then $ G $ contains either a red copy of $ G_1 $ or a blue copy of $ G_2 $. Let $ nK_2 $ be a matching with $ n $ edges and $ P_4 $ a path with four vertices. Rahadjeng, Baskoro, and Assiyatun [Procedia Comput. Sci. 74 (2015), 32-37] conjectured that $ \hat{r}_{c}(nK_2, P_4) = 3n-1 $ if $ n $ is even, and $ \hat{r}_{c}(nK_2, P_4) = 3n $ otherwise. We verify the conjecture in this short paper.

References

[1]	H. Assiyatun, B. Rahadjeng, E. T. Baskoro, The connected size Ramsey number for matchings versus small disconnected graphs, Electron. J. Graph Theory Appl., 7 (2019), 113–119. http://dx.doi.org/10.5614/ejgta.2019.7.1.9 doi: 10.5614/ejgta.2019.7.1.9
[2]	J. Beck, On size Ramsey number of paths, trees, and circuits. Ⅰ, J. Graph Theory, 7 (1983), 115–129. https://doi.org/10.1002/jgt.3190070115 doi: 10.1002/jgt.3190070115
[3]	J. A. Bondy, U. S. R. Murty, Graph theory, Springer, 2008. https://doi.org/10.1007/978-1-84628-970-5
[4]	S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp, Ramsey-minimal graphs for multiple copies, Indag. Math. (N.S.), 81 (1978), 187–195. https://doi.org/10.1016/1385-7258(78)90036-7 doi: 10.1016/1385-7258(78)90036-7
[5]	A. Davoodi, R. Javadi, A. Kamranian, G. Raeisi, On a conjecture of Erdős on size Ramsey number of star forests, arXiv: 2111.02065, 2021. Available from: https://arXiv.org/abs/2111.02065
[6]	Jr. D. Dellamonica, The size‐Ramsey number of trees, Random Struct. Algor., 40 (2012), 49–73. https://doi.org/10.1002/rsa.20363 doi: 10.1002/rsa.20363
[7]	A. Dudek, P. Prałat, On some multicolor Ramsey properties of random graphs, SIAM J. Discrete Math., 31 (2017), 2079–2092. https://doi.org/10.1137/16M1069717 doi: 10.1137/16M1069717
[8]	P. Erdős, R. J. Faudree, Size Ramsey numbers involving matchings, Finite and Infinite Sets, (1984), 247–264. https://doi.org/10.1016/B978-0-444-86893-0.50019-X doi: 10.1016/B978-0-444-86893-0.50019-X
[9]	P. Erdős, R. J. Faudree, C. C Rousseau, R. H. Schelp, The size Ramsey number, Period. Math. Hungar., 9 (1978), 145–161. https://doi.org/10.1007/BF02018930 doi: 10.1007/BF02018930
[10]	R. J. Faudree, J. Sheehan, Size Ramsey numbers for small‐order graphs, J. Graph Theory, 7 (1983), 53–55. https://doi.org/10.1002/jgt.3190070107 doi: 10.1002/jgt.3190070107
[11]	R. J. Faudree, J. Sheehan, Size Ramsey numbers involving stars, Discrete Math., 46 (1983), 151–157. https://doi.org/10.1016/0012-365X(83)90248-0 doi: 10.1016/0012-365X(83)90248-0
[12]	F. Harary, Z. Miller, Generalized Ramsey theory Ⅷ, The size Ramsey number of small graphs, In Studies in Pure Mathematics, (1983), 271–283. https://doi.org/10.1007/978-3-0348-5438-2_25
[13]	P. E. Haxell, Y. Kohayakawa, The size-Ramsey number of trees, Israel J. Math., 89 (1995), 261–274. https://doi.org/10.1007/BF02808204 doi: 10.1007/BF02808204
[14]	P. E. Haxell, Y. Kohayakawa, T. Łuczak, The induced size-Ramsey number of cycles, Combin. Probab. Comput., 4 (1995), 217–239. https://doi.org/10.1017/S0963548300001619 doi: 10.1017/S0963548300001619
[15]	R. Javadi, F. Khoeini, G. R. Omidi, A. Pokrovskiy, On the size-Ramsey number of cycles, Combin. Probab. Comput., 28 (2019), 871–880. https://doi.org/10.1017/S0963548319000221 doi: 10.1017/S0963548319000221
[16]	R. Javadi, G. Omidi, On a question of Erdős and Faudree on the size Ramsey numbers, SIAM J. Discrete Math., 32 (2018), 2217–2228. https://doi.org/10.1137/17M1115022 doi: 10.1137/17M1115022
[17]	R. Lortz, I. Mengersen, Size Ramsey results for paths versus stars, Australas. J. Combin., 18 (1998), 3–12.
[18]	R. Lortz, I. Mengersen, Size Ramsey results for the path of order three, Graphs Combin., 37 (2021), 2315–2331. https://doi.org/10.1007/s00373-021-02398-3 doi: 10.1007/s00373-021-02398-3
[19]	M. Miralaei, G. R. Omidi, M. Shahsiah, Size Ramsey numbers of stars versus cliques, J. Graph Theory, 92 (2019), 275–286. https://doi.org/10.1002/jgt.22453 doi: 10.1002/jgt.22453
[20]	B. Rahadjeng, E. T. Baskoro, H. Assiyatun, Connected size Ramsey numbers for matchings versus cycles or paths, Procedia Comput. Sci., 74 (2015), 32–37. https://doi.org/10.1016/j.procs.2015.12.071 doi: 10.1016/j.procs.2015.12.071
[21]	B. Rahadjeng, E. T. Baskoro, H. Assiyatun, Connected size Ramsey numbers of matchings and stars, AIP Conf. Proc., 1707 (2016), 020015. https://doi.org/10.1063/1.4940816 doi: 10.1063/1.4940816
[22]	B. Rahadjeng, E. T. Baskoro, H. Assiyatun, Connected size Ramsey number for matchings vs. small stars or cycles, Proc. Indian Acad. Sci.: Math. Sci., 127 (2017), 787–792. https://doi.org/10.1007/s12044-017-0366-z doi: 10.1007/s12044-017-0366-z
[23]	J. Sheehan, R. J. Faudree, C. C. Rousseau, A class of size Ramsey problems involving stars, Graph Theory and Combinatorics, (1983), 273–281.
[24]	V. Vito, A. C. Nabila, E. Safitri, D. R. Silaban, The size Ramsey and connected size Ramsey numbers for matchings versus paths, J. Phys. Conf. Ser., 1725 (2021), 012098. https://doi.org/10.1088/1742-6596/1725/1/012098 doi: 10.1088/1742-6596/1725/1/012098
[25]	V. Vito, D. R. Silaban, Two types of size Ramsey numbers for matchings of small order, J. Discrete Math. Sci. Cryptogr., (2022), 1–13. https://doi.org/10.1080/09720529.2021.2000153 doi: 10.1080/09720529.2021.2000153
[26]	S. Wang, R. Song, Y. Zhang, Y. Zhang, Connected size Ramsey numbers of matchings versus a small path or cycle, arXiv: 2205.03965, 2022. Available from: https://arXiv.org/abs/2205.03965

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)