Ramsey numbers for complete graphs versus generalized fans. (English) Zbl 1502.05160
Summary: For two graphs \(G\) and \(H\), let \(r(G, H)\) and \(r_\ast(G,H)\) denote the Ramsey number and star-critical Ramsey number of \(G\) versus \(H\), respectively. Y. Li and C. C. Rousseau [J. Graph Theory 23, No. 4, 413–420 (1996; Zbl 0954.05031)] proved that \(r(K_m,F_{t,n})=tn(m-1)+1\) for \(m\ge 3\) and sufficiently large \(n\), where \(F_{t,n}=K_1+nK_t\). Recently, Y. Hao and Q. Lin [Discrete Appl. Math. 251, 345–348 (2018; Zbl 1401.05294)] proved that \(r(K_3,F_{3,n})=6n+1\) for \(n\ge 3\) and \(r_\ast(K_3,F_{3,n})=3n+3\) for \(n\ge 4\). In this paper, we show that \(r(K_m, sF_{t,n})=tn(m+s-2)+s\) for sufficiently large \(n\) and, in particular, \(r(K_3, sF_{t,n})=tn(s+1)+s\) for \(t\in \{3,4\}\), \(n\ge t\) and \(s\ge 1\). We also show that \(r_\ast(K_3, F_{4,n})=4n+4\) for \(n\ge 4\) and establish an upper bound for \(r(F_{2,m},F_{t,n})\).
Software:
pyuvdataReferences:
| [1] | Baskoro Surahmat, ET; Broersma, HJ, The Ramsey numbers of fans versus \(K_4\), Bull. Inst. Combin. Appl., 43, 96-102 (2005) · Zbl 1067.05049 |
| [2] | Burr, S., Ramsey numbers involving graphs with long suspended paths, J. Lond. Math. Soc., 2, 405-413 (1981) · Zbl 0474.05051 · doi:10.1112/jlms/s2-24.3.405 |
| [3] | Burr, S.; Erdős, P.; Spencer, JH, Ramsey theorems for multiple copies of graphs, Trans. Am. Math. Soc., 209, 87-99 (1975) · Zbl 0273.05111 · doi:10.1090/S0002-9947-1975-0409255-0 |
| [4] | Chen, Y.; Zhang, Y., The Ramsey numbers of fans versus a complete graph of order five, Electron. J. Graph Theory Appl., 2, 66-69 (2014) · Zbl 1306.05153 · doi:10.5614/ejgta.2014.2.1.6 |
| [5] | Chen, G.; Yu, X.; Zhao, Y., Improved bounds on the Ramsey number of fans, Eur. J. Combin., 96 (2021) · Zbl 1466.05126 · doi:10.1016/j.ejc.2021.103347 |
| [6] | Dvořák, V., Metrebian, H.: A new upper bound for the Ramsey number of fans. Preprint available at arXiv:2109.07935 · Zbl 1512.05287 |
| [7] | Gupta, L.; Gupta, SK; Sudan, A., On Ramsey numbers for fan-fan graphs, J. Combin. Inf. Syst. Sci., 22, 85-93 (1997) · Zbl 0916.05053 |
| [8] | Haghi, S.; Maimani, HR; Seify, A., Star-critical Ramsey number of \(F_n\) versus \(K_4\), Discrete Appl. Math., 217, 203-209 (2017) · Zbl 1358.05186 · doi:10.1016/j.dam.2016.09.012 |
| [9] | Hajnal, A., Szemerédi, E.: Proof of a conjecture of P. Erdős. In Combinational Theory and Its Applications, pp. 601-623 (1970) · Zbl 0217.02601 |
| [10] | Hamm, A.; Hazelton, P.; Thompson, S., On Ramsey and star-critical Ramsey number for generalized fans versus \(nK_m\), Discrete Appl. Math., 305, 64-70 (2021) · Zbl 1476.05133 · doi:10.1016/j.dam.2021.08.027 |
| [11] | Hao, Y.; Lin, Q., Ramsey number of \(K_3\) versus \(F_{3, n}\), Discrete Appl. Math., 251, 345-348 (2018) · Zbl 1401.05294 · doi:10.1016/j.dam.2018.05.056 |
| [12] | Hao, Y.; Lin, Q., Star-critical Ramsey numbers for large generalized fans and books, Discrete Math., 341, 3385-3393 (2018) · Zbl 1397.05194 · doi:10.1016/j.disc.2018.08.025 |
| [13] | Hook, J.; Isaak, G., Star-critical Ramsey numbers, Discrete Appl. Math., 159, 328-334 (2011) · Zbl 1207.05212 · doi:10.1016/j.dam.2010.11.007 |
| [14] | Kadota, S.; Onozuka, T.; Suzuki, Y., The graph Ramsey number \(R(F_l, K_6)\), Discrete Math., 342, 1028-1037 (2019) · Zbl 1405.05111 · doi:10.1016/j.disc.2018.12.016 |
| [15] | Li, Z.; Li, Y., Some star-critical Ramsey numbers, Discrete Appl. Math., 182, 301-305 (2015) · Zbl 1304.05100 · doi:10.1016/j.dam.2014.09.014 |
| [16] | Li, Y.; Rousseau, CC, Fan-complete graph Ramsey numbers, J. Graph Theory, 23, 413-420 (1996) · Zbl 0954.05031 · doi:10.1002/(SICI)1097-0118(199612)23:4<413::AID-JGT10>3.0.CO;2-D |
| [17] | Li, Y.; Li, Y.; Wang, Y., Star-critical Ramsey numbers of generalized fans, Graphs Comb., 37, 2113-2120 (2021) · Zbl 1479.05220 · doi:10.1007/s00373-021-02337-2 |
| [18] | Lin, Q.; Li, Y., On Ramsey numbers of fans, Discrete Appl. Math., 157, 191-194 (2009) · Zbl 1159.05034 · doi:10.1016/j.dam.2008.05.004 |
| [19] | Lin, Q.; Li, Y.; Dong, L., Ramsey goodness and generalized stars, Eur. J. Combin., 31, 1228-1234 (2010) · Zbl 1205.05157 · doi:10.1016/j.ejc.2009.10.011 |
| [20] | Lorimer, PJ, Ramsey number for quadrangles and triangles, J. Comb. Theory Ser. B, 23, 262-265 (1977) · Zbl 0339.05116 · doi:10.1016/0095-8956(77)90041-7 |
| [21] | Radziszowski, S.P.: Small Ramsey numbers. Electron. J. Combin. DS1.16 http://www.combinatorics.org (2021) · Zbl 0953.05048 |
| [22] | Zhang, Y.; Broersma, H.; Chen, Y., A note on Rasmey numbers for fans, Bull. Aust. Math. Soc., 92, 19-23 (2015) · Zbl 1319.05134 · doi:10.1017/S0004972715000398 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
