On path-quasar Ramsey numbers

Binlong Li; Bo Ning

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

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

Abstract

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

How to cite

top

Binlong Li, and Bo Ning. "On path-quasar Ramsey numbers." Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica 68.2 (2014): null. <http://eudml.org/doc/289774>.

@article{BinlongLi2014,
abstract = {Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline\{G\}$ contains a $G_2$. Parsons gave a recursive formula to determine the values of $R(P_n,K_\{1,m\})$, where $P_n$ is a path on $n$ vertices and $K_\{1,m\}$ is a star on $m+1$ vertices. In this note, we study the Ramsey numbers $R(P_n,K_1\vee F_m)$, where $F_m$ is a linear forest on $m$ vertices. We determine the exact values of $R(P_n,K_1\vee F_m)$ for the cases $m\le n$ and $m\ge 2n$, and for the case that $F_m$ has no odd component. Moreover, we give a lower bound and an upper bound for the case $n+1\le m\le 2n-1$ and $F_m$ has at least one odd component.},
author = {Binlong Li, Bo Ning},
journal = {Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica},
keywords = {},
language = {eng},
number = {2},
pages = {null},
title = {On path-quasar Ramsey numbers},
url = {http://eudml.org/doc/289774},
volume = {68},
year = {2014},
}

TY - JOUR
AU - Binlong Li
AU - Bo Ning
TI - On path-quasar Ramsey numbers
JO - Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
PY - 2014
VL - 68
IS - 2
SP - null
AB - Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$. Parsons gave a recursive formula to determine the values of $R(P_n,K_{1,m})$, where $P_n$ is a path on $n$ vertices and $K_{1,m}$ is a star on $m+1$ vertices. In this note, we study the Ramsey numbers $R(P_n,K_1\vee F_m)$, where $F_m$ is a linear forest on $m$ vertices. We determine the exact values of $R(P_n,K_1\vee F_m)$ for the cases $m\le n$ and $m\ge 2n$, and for the case that $F_m$ has no odd component. Moreover, we give a lower bound and an upper bound for the case $n+1\le m\le 2n-1$ and $F_m$ has at least one odd component.
LA - eng
KW -
UR - http://eudml.org/doc/289774
ER -

References

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

NotesEmbed ?

top

You must be logged in to post comments.