Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Ramsey numbers for the pair sparse graph-path or cycle


Authors: S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp
Journal: Trans. Amer. Math. Soc. 269 (1982), 501-512
MSC: Primary 05C55
MathSciNet review: 637704
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ G$ be a connected graph on $ n$ vertices with no more than $ n(1 + \varepsilon )$ edges, and $ {P_k}$ or $ {C_k}$ a path or cycle with $ k$ vertices. In this paper we will show that if $ n$ is sufficiently large and $ \varepsilon $ is sufficiently small then for $ k$ odd

$\displaystyle r(G,\,{C_k}) = 2n - 1.$

Also, for $ k \geqslant 2$,

$\displaystyle r(G,\,{P_k}) = \max \{ n + [k/2] - 1,\,n + k - 2 - \alpha \prime - \delta \} ,$

where $ \alpha \prime $ is the independence number of an appropriate subgraph of $ G$ and $ \delta $ is 0 or $ 1$ depending upon $ n$, $ k$ and $ \alpha \prime $.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C55

Retrieve articles in all journals with MSC: 05C55


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1982-0637704-5
PII: S 0002-9947(1982)0637704-5
Article copyright: © Copyright 1982 American Mathematical Society