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

Halina Bielak; Kinga Dąbrowska

Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica (2015)

  • Volume: 69, Issue: 2
  • ISSN: 0365-1029

Abstract

top
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 F ¯ contains H as a subgraph, where 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.

How to cite

top

Halina Bielak, and Kinga Dąbrowska. "The Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths." Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica 69.2 (2015): null. <http://eudml.org/doc/289826>.

@article{HalinaBielak2015,
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.},
author = {Halina Bielak, Kinga Dąbrowska},
journal = {Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica},
keywords = {Cycle; path; Ramsey number; Turan number},
language = {eng},
number = {2},
pages = {null},
title = {The Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths},
url = {http://eudml.org/doc/289826},
volume = {69},
year = {2015},
}

TY - JOUR
AU - Halina Bielak
AU - Kinga Dąbrowska
TI - The Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths
JO - Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
PY - 2015
VL - 69
IS - 2
SP - null
AB - 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.
LA - eng
KW - Cycle; path; Ramsey number; Turan number
UR - http://eudml.org/doc/289826
ER -

References

top
  1. Burr, S. A., Ramsey numbers involving graphs with long suspended paths, 
  2. J. London Math. Soc. 24 (2) (1981), 405-413. 
  3. Burr, S. A., Erdos, P., Generalization of a Ramsey-theoretic result of Chvatal, J. Graph Theory 7 (1983), 39-51. 
  4. Chen, Y., Cheng, T. C. E., Ng, C. T., Zhang, Y., A theorem on cycle-wheel Ramsey number, Discrete Math. 312 (2012), 1059-1061. 
  5. 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. 
  6. Chen, Y., Zhang, Y., Zhang, K., The Ramsey numbers of paths versus wheels, Discrete Math. 290 (2005), 85-87. 
  7. Faudree, R. J., Lawrence, S. L., Parsons, T. D., Schelp, R. H., Path-cycle Ramsey numbers, Discrete Math. 10 (1974), 269-277. 
  8. Faudree, R. J., Schelp, R. H., All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974), 313-329. 
  9. Karolyi, G., Rosta, V., Generalized and geometric Ramsey numbers for cycles, Theoretical Computer Science 263 (2001), 87-98. 
  10. Lin, Q., Li, Y., Dong, L., Ramsey goodness and generalized stars, Europ. J. Combin. 31 (2010), 1228-1234. 
  11. Radziszowski, S. P., Small Ramsey numbers, The Electronic Journal of Combinatorics (2014), DS1.14. 
  12. Radziszowski, S. P., Xia, J., Paths, cycles and wheels without antitriangles, 
  13. Australasian J. Combin. 9 (1994), 221-232. 
  14. 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. 
  15. Salman, A. N. M., Broersma, H. J., On Ramsey numbers for paths versus wheels, Discrete Math. 307 (2007), 975-982. 
  16. Shi, L., Ramsey numbers of long cycles versus books or wheels, European J. Combin. 31 (2010), 828-838. 
  17. Surahmat, Baskoro, E. T., Broersma, H. J., The Ramsey numbers of large cycles versus small wheels, Integers 4 (2004), A10. 
  18. Surahmat, Baskoro, E. T., Tomescu, I., The Ramsey numbers of large cycles versus odd wheels, Graphs Combin. 24 (2008), 53-58. 
  19. Surahmat, Baskoro, E. T., Tomescu, I., The Ramsey numbers of large cycles versus wheels, Discrete Math. 306 (24) (2006), 3334-3337. 
  20. Zhang, Y., On Ramsey numbers of short paths versus large wheels, Ars Combin. 89 (2008), 11-20. 
  21. Zhang, L., Chen, Y., Cheng, T. C., The Ramsey numbers for cycles versus wheels of even order, European J. Combin. 31 (2010), 254-259. 
  22. Zhang, Y., Chen, Y., The Ramsey numbers of wheels versus odd cycles, Discrete Math. 323 (2014), 76-80. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.