The Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths

Halina Bielak, Kinga Dąbrowska

Abstract


The Ramsey number \(R(G, H)\) for a pair of graphs \(G\) and \(H\) is defined as the smallest integer \(n\) such that, for any graph \(F\) on \(n\) vertices, either \(F\) contains \(G\) or \(\overline{F}\) contains \(H\) as a subgraph, where \(\overline{F}\) denotes the complement of \(F\). We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers \(R(K_1+L_n, P_m)\) and \(R(K_1+L_n, C_m)\) for some integers \(m\), \(n\), where \(L_n\) is a linear forest of order \(n\) with at least one edge.

Keywords


Cycle; path; Ramsey number; Turan number

Full Text:

PDF

References


Burr, S. A., Ramsey numbers involving graphs with long suspended paths,

J. London Math. Soc. 24 (2) (1981), 405-413.

Burr, S. A., Erdos, P., Generalization of a Ramsey-theoretic result of Chvatal, J. Graph Theory 7 (1983), 39-51.

Chen, Y., Cheng, T. C. E., Ng, C. T., Zhang, Y., A theorem on cycle-wheel Ramsey number, Discrete Math. 312 (2012), 1059-1061.

Chen, Y., Cheng, T. C. E., Miao, Z., Ng, C. T., The Ramsey numbers for cycles versus wheels of odd order, Appl. Math. Letters 22 (2009), 875-1876.

Chen, Y., Zhang, Y., Zhang, K., The Ramsey numbers of paths versus wheels, Discrete Math. 290 (2005), 85-87.

Faudree, R. J., Lawrence, S. L., Parsons, T. D., Schelp, R. H., Path-cycle Ramsey numbers, Discrete Math. 10 (1974), 269-277.

Faudree, R. J., Schelp, R. H., All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974), 313-329.

Karolyi, G., Rosta, V., Generalized and geometric Ramsey numbers for cycles, Theoretical Computer Science 263 (2001), 87-98.

Lin, Q., Li, Y., Dong, L., Ramsey goodness and generalized stars, Europ. J. Combin. 31 (2010), 1228-1234.

Radziszowski, S. P., Small Ramsey numbers, The Electronic Journal of Combinatorics (2014), DS1.14.

Radziszowski, S. P., Xia, J., Paths, cycles and wheels without antitriangles,

Australasian J. Combin. 9 (1994), 221-232.

Rosta, V.,On a Ramsey type problem of J. A. Bondy and P. Erdos, I, II, J. Combin. Theory Ser. B 15 (1973), 94-120.

Salman, A. N. M., Broersma, H. J., On Ramsey numbers for paths versus wheels, Discrete Math. 307 (2007), 975-982.

Shi, L., Ramsey numbers of long cycles versus books or wheels, European J. Combin. 31 (2010), 828-838.

Surahmat, Baskoro, E. T., Broersma, H. J., The Ramsey numbers of large cycles versus small wheels, Integers 4 (2004), A10.

Surahmat, Baskoro, E. T., Tomescu, I., The Ramsey numbers of large cycles versus odd wheels, Graphs Combin. 24 (2008), 53-58.

Surahmat, Baskoro, E. T., Tomescu, I., The Ramsey numbers of large cycles versus wheels, Discrete Math. 306 (24) (2006), 3334-3337.

Zhang, Y., On Ramsey numbers of short paths versus large wheels, Ars Combin. 89 (2008), 11-20.

Zhang, L., Chen, Y., Cheng, T. C., The Ramsey numbers for cycles versus wheels of even order, European J. Combin. 31 (2010), 254-259.

Zhang, Y., Chen, Y., The Ramsey numbers of wheels versus odd cycles, Discrete Math. 323 (2014), 76-80.




DOI: http://dx.doi.org/10.17951/a.2015.69.2.1-7
Date of publication: 2015-12-30 22:51:59
Date of submission: 2015-12-29 21:01:57


Statistics


Total abstract view - 770
Downloads (from 2020-06-17) - PDF - 470

Indicators



Refbacks

  • There are currently no refbacks.


Copyright (c) 2015 Halina Bielak, Kinga Dąbrowska