On path-quasar Ramsey numbers

Binlong Li; Bo Ning

Annales UMCS, Mathematica (2015)

  • Volume: 68, Issue: 2, page 11-17
  • ISSN: 2083-7402

Abstract

top
Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or Ḡ contains a G2. Parsons gave a recursive formula to determine the values of R(Pn,K1,m), where Pn is a path on n vertices and K1,m is a star on m+1 vertices. In this note, we study the Ramsey numbers R(Pn,K1,m), where Pn is a linear forest on m vertices. We determine the exact values of R(Pn,K1∨Fm) for the cases m ≤ n and m ≥ 2n, and for the case that Fm has no odd component. Moreover, we give a lower bound and an upper bound for the case n+1 ≤ m ≤ 2n−1 and Fm has at least one odd component.

How to cite

top

Binlong Li, and Bo Ning. "On path-quasar Ramsey numbers." Annales UMCS, Mathematica 68.2 (2015): 11-17. <http://eudml.org/doc/270004>.

@article{BinlongLi2015,
abstract = {Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or Ḡ contains a G2. Parsons gave a recursive formula to determine the values of R(Pn,K1,m), where Pn is a path on n vertices and K1,m is a star on m+1 vertices. In this note, we study the Ramsey numbers R(Pn,K1,m), where Pn is a linear forest on m vertices. We determine the exact values of R(Pn,K1∨Fm) for the cases m ≤ n and m ≥ 2n, and for the case that Fm has no odd component. Moreover, we give a lower bound and an upper bound for the case n+1 ≤ m ≤ 2n−1 and Fm has at least one odd component.},
author = {Binlong Li, Bo Ning},
journal = {Annales UMCS, Mathematica},
keywords = {Ramsey number; path; star; quasar},
language = {eng},
number = {2},
pages = {11-17},
title = {On path-quasar Ramsey numbers},
url = {http://eudml.org/doc/270004},
volume = {68},
year = {2015},
}

TY - JOUR
AU - Binlong Li
AU - Bo Ning
TI - On path-quasar Ramsey numbers
JO - Annales UMCS, Mathematica
PY - 2015
VL - 68
IS - 2
SP - 11
EP - 17
AB - Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or Ḡ contains a G2. Parsons gave a recursive formula to determine the values of R(Pn,K1,m), where Pn is a path on n vertices and K1,m is a star on m+1 vertices. In this note, we study the Ramsey numbers R(Pn,K1,m), where Pn is a linear forest on m vertices. We determine the exact values of R(Pn,K1∨Fm) for the cases m ≤ n and m ≥ 2n, and for the case that Fm has no odd component. Moreover, we give a lower bound and an upper bound for the case n+1 ≤ m ≤ 2n−1 and Fm has at least one odd component.
LA - eng
KW - Ramsey number; path; star; quasar
UR - http://eudml.org/doc/270004
ER -

References

top
  1. [1] Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976. Zbl1226.05083
  2. [2] Chen, Y., Zhang, Y., Zhang, K., The Ramsey numbers of paths versus wheels, Discrete Math. 290 (1) (2005), 85-87.[WoS] Zbl1059.05074
  3. [3] Dirac, G. A., Some theorems on abstract graphs, Proc. London. Math. Soc. 2 (1952), 69-81. Zbl0047.17001
  4. [4] Faudree, R. J., Lawrence, S. L., Parsons, T. D., Schelp, R. H., Path-cycle Ramsey numbers, Discrete Math. 10 (2) (1974), 269-277.[Crossref] Zbl0293.05120
  5. [5] Graham, R. L., Rothschild, B. L., Spencer, J. H., Ramsey Theory, Second Edition, John Wiley & Sons Inc., New York, 1990. 
  6. [6] Li, B., Ning, B., The Ramsey numbers of paths versus wheels: a complete solution, Electron. J. Combin. 21 (4) (2014), #P4.41. Zbl1305.05140
  7. [7] Parsons, T. D., Path-star Ramsey numbers, J. Combin. Theory, Ser. B 17 (1) (1974), 51-58. Zbl0282.05110
  8. [8] Rousseau, C. C., Sheehan, J., A class of Ramsey problems involving trees, J. London Math. Soc. 2 (3) (1978), 392-396.[Crossref] Zbl0393.05037
  9. [9] Salman, A. N. M., Broersma, H. J., Path-fan Ramsey numbers, Discrete Applied Math. 154 (9) (2006), 1429-1436. Zbl1093.05043
  10. [10] Salman, A. N. M., Broersma, H. J., Path-kipas Ramsey numbers, Discrete Applied Math. 155 (14) (2007), 1878-1884.[WoS] Zbl1128.05037
  11. [11] Zhang, Y., On Ramsey numbers of short paths versus large wheels, Ars Combin. 89 (2008), 11-20. Zbl1224.05346

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.