✦ LIBER ✦

On cycle—Complete graph ramsey numbers

✍ Scribed by P. Erdös; R. J. Faudree; C. C. Rousseau; R. H. Schelp

Publisher: John Wiley and Sons
Year: 1978
Tongue: English
Weight: 507 KB
Volume: 2
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190020107

No coin nor oath required. For personal study only.

✦ Synopsis

A new upper bound is given for the cycle-complete graph Ramsey number r(Cm, K,,), the smallest order for a graph which forces it to contain either a cycle of order m or a set of n independent vertices. Then, another cycle-complete graph Ramsey number is studied, namely r(sCm, K,) the smallest order for a graph which forces it to contain either a cycle of order I for some I satisfying 3 I I s m or a set of n independent vertices. We obtain the exact value of r(sCm, K,,) for all m > n arid an upper bound which applies when m is large in comparison with log n.

📜 SIMILAR VOLUMES

On Book-Complete Graph Ramsey Numbers

✍ Yusheng Li; C.C. Rousseau 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 274 KB

It is shown that a graph of order N and average degree d that does not contain the book B m =K 1 +K 1, m as a subgraph has independence number at least Nf (d ), where f (x)t(log xÂx) (x Ä ). From this result we find that the book-complete graph Ramsey number satisfies r(B m , K n ) mn 2 Âlog(nÂe). I

Fan-complete graph Ramsey numbers

✍ Li, Yusheng; Rousseau, Cecil C. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB 👁 2 views

It is shown that if G and H are arbitrary fixed graphs and n is sufficiently large, then Also, we prove that r ( K 1 +F, K,) 5 (m+o(l))&(n -+ GO) for any forest Fwhose largest component has m edges. Thus r(Fe, K,) 5 (1 + o(l))&, where Fe = K1 + CK2. We conjecture that r(Fe, K,) -&(n + cm).

Tree-complete graph ramsey numbers

✍ V. Chvátal 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 50 KB

## Abstract The ramsey number of any tree of order __m__ and the complete graph of order __n__ is 1 + (__m__ − 1)(__n__ − 1).

All cycle-complete graph Ramsey numbers

All cycle-complete graph Ramsey numbers r(Cm, K6)

✍ Ingo Schiermeyer 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract The cycle‐complete graph Ramsey number __r__(__C~m~__, __K~n~__) is the smallest integer __N__ such that every graph __G__ of order __N__ contains a cycle __C~m~__ on __m__ vertices or has independence number α(__G__) ≥ __n__. It has been conjectured by Erdős, Faudree, Rousseau and Sche

On ramsey numbers of forests versus near

On ramsey numbers of forests versus nearly complete graphs

✍ Gary Chartrand; Ronald J. Gould; Albert D. Polimeni 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 1 views

## Abstract A formula is presented for the ramsey number of any forest of order at least 3 versus any graph __G__ of order __n__ ≥ 4 having clique number __n__ ‐ 1. In particular, if __T__ is a tree of order __m__ ≥ 3, then __r(T, G)__ = 1 + (__m__ ‐ 1)(__n__ ‐ 2).

The ramsey numbers for stripes and one c

The ramsey numbers for stripes and one complete graph

✍ Peter Lorimer 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 244 KB 👁 1 views

The Ramsey numbers M,,, n,P,, ..., n,P,), p > 2, are calculated. ## 1. Introduction One class of generalized Ramsey numbers that are known exactly are those for the graphs nP2 which consist of n disjoint paths of length 2; E. J. Cockayne and the author proved in 111 that d r(nlp2, ..., n d P 2 ) =