Some star-critical connected Ramsey numbers

Articles in Press

Document Type : Research Paper

Authors

School of Mathematical Sciences, Hebei Normal University, Shijiazhuang, China

Abstract

The star-critical connected Ramsey number $r_c^*(G,H)$, introduced by Moun, Jakhar, and Budden (\textit{TOC}, 2025), is a more deeply studied variant of the connected Ramsey number. For paths versus complete graphs, they obtained the exact values of $r_c^*(P_m,K_n)$ when $m=5$ and when $n=3$. For stars versus complete graphs, they determined the exact values of $r_c^*(K_{1,m},K_n)$ when $m=3$ and when $n=3$. We complete the generalization of both cases by establishing the exact values of $r_c^*(P_m,K_n)$ for $m\ge 6$ and $n\ge 4$, and $r_c^*(K_{1,m},K_n)$ for $m\ge 4$ and $n\ge 4$. The former result disproves a conjecture proposed by Moun et al. (\textit{TOC}, 2025).

Keywords

Main Subjects

References

[1] M. R. Budden, Star-critical Ramsey numbers for graphs, SpringerBriefs in Mathematics, Springer, Cham, 2023.
[2] M. Budden, Ramsey numbers for connected 2-colorings of complete graphs, Theory Appl. Graphs, 10 no. 1 Art. 7 (2023) 10 pp.
[3] M. Budden and T. Wimbish, Connected Ramsey numbers involving trees, Electron. J. Math. 9 (2025) 31–37.
[4] V. Chv´atal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 no. 1 (1977) 93–93.
[5] R. J. Faudree and R. H. Schelp, Connected Ramsey numbers for paths and stars, Colloq. Math. Soc. J´anos Bolyai, 18 (1976) 307–313.
[6] R. J. Faudree and R. H. Schelp, Some connected Ramsey numbers, J. Graph Theory, 2 2 (1978) 119–128.
[7] R. J. Faudree and R. H. Schelp, Some problems in Ramsey theory, Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Math., Springer, Berlin-New York, (1978) 500–515.
[8] R. H¨aggkvist, R. J. Faudree and R. H. Schelp, Pancyclic graphs-connected Ramsey number, Ars Combin., 11 (1981) 37–49.
[9] J. Hook, The classification of critical graphs and star-critical Ramsey numbers, (Ph.D.)–Lehigh University, ProQuest LLC, Ann Arbor, MI, 2010, 110 pp.
[10] J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math., 159 no. 5 (2011) 328–334.
[11] M. Moun, J. Jakhar and M. Budden, Star-critical connected Ramsey numbers for 2-colorings of complete graphs, Trans. Combin., 14 no. 4 (2025) 211–222.
[12] S. P. Radziszowski, Small Ramsey numbers – revision #17, Electron. J. Combin., DS1.17 (2024) 133 pp.
[13] F. Ramsey, On a problem of formal logic, Proc. London Math. Soc. (2), 30 no. 4 (1929) 264–286.
[14] J. S. Sherr, General and connected Ramsey theory for graphs, Thesis (Ph.D.)–Emory University. ProQuest LLC, Ann Arbor, MI, 1987, 89 pp.
[15] D. P. Sumner, The connected Ramsey number, Discrete Math., 22 no. 1 (1978) 49–55.
[16] Y. Zhang, H. Broersma and Y. Chen, On star-critical and upper size Ramsey numbers, Discrete Appl. Math., 202 (2016) 174–180.
Transactions on Combinatorics

Articles in Press, Corrected Proof
Available Online from 21 February 2026

Files

History

  • Receive Date: 08 April 2025
  • Revise Date: 08 February 2026
  • Accept Date: 14 February 2026
  • Published Online: 21 February 2026

Share

How to cite

Statistics