PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 68 | 2 |
Tytuł artykułu

On path-quasar Ramsey numbers

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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\leq n\) and \(m\geq 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\leq m\leq 2n-1\) and \(F_m\) has at least one odd component.
Słowa kluczowe
EN
 
Rocznik
Tom
68
Numer
2
Opis fizyczny
Daty
wydano
2014
online
2015-05-23
Twórcy
autor
autor
Bibliografia
  • Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.
  • Chen, Y., Zhang, Y., Zhang, K., The Ramsey numbers of paths versus wheels, Discrete Math. 290 (1) (2005), 85–87.
  • Dirac, G. A., Some theorems on abstract graphs, Proc. London. Math. Soc. 2 (1952), 69–81.
  • Faudree, R. J., Lawrence, S. L., Parsons, T. D., Schelp, R. H., Path-cycle Ramsey numbers, Discrete Math. 10 (2) (1974), 269–277.
  • Graham, R. L., Rothschild, B. L., Spencer, J. H., Ramsey Theory, Second Edition, John Wiley & Sons Inc., New York, 1990.
  • Li, B., Ning, B., The Ramsey numbers of paths versus wheels: a complete solution, Electron. J. Combin. 21 (4) (2014), #P4.41.
  • Parsons, T. D., Path-star Ramsey numbers, J. Combin. Theory, Ser. B 17 (1) (1974), 51–58.
  • Rousseau, C. C., Sheehan, J., A class of Ramsey problems involving trees, J. London Math. Soc. 2 (3) (1978), 392–396.
  • Salman, A. N. M., Broersma, H. J., Path-fan Ramsey numbers, Discrete Applied Math. 154 (9) (2006), 1429–1436.
  • Salman, A. N. M., Broersma, H. J., Path-kipas Ramsey numbers, Discrete Applied Math. 155 (14) (2007), 1878–1884.
  • Zhang, Y., On Ramsey numbers of short paths versus large wheels, Ars Combin. 89 (2008), 11–20.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ojs-doi-10_17951_a_2014_68_2_11
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.