𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Ramsey unsaturated and saturated graphs

✍ Scribed by P. Balister; J. Lehel; R.H. Schelp

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
119 KB
Volume
51
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph is Ramsey unsaturated if there exists a proper supergraph of the same order with the same Ramsey number, and Ramsey saturated otherwise. We present some conjectures and results concerning both Ramsey saturated and unsaturated graphs. In particular, we show that cycles C~n~ and paths P~n~ on n vertices are Ramsey unsaturated for all n ≥ 5. © 2005 Wiley Periodicals, Inc.

📜 SIMILAR VOLUMES

Generalized Split Graphs and Ramsey Numb
Generalized Split Graphs and Ramsey Numbers
✍ András Gyárfás 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 283 KB

A graph G is called a ( p, q)-split graph if its vertex set can be partitioned into A, B so that the order of the largest independent set in A is at most p and the order of the largest complete subgraph in B is at most q. Applying a well-known theorem of Erdo s and Rado for 2-systems, it is shown th

Detour-saturated graphs
Detour-saturated graphs
✍ Lowell W. Beineke; J. E. Dunbar; M. Frick 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB

## Abstract A graph is said to be detour‐saturated if the addition of any edge results in an increased greatest path length. In this paper, we add to the relatively small amount that is known about detour‐saturated graphs. Our main result is a determination of all connected detour‐saturated graphs

Ramsey linear families and generalized s
Ramsey linear families and generalized subdivided graphs
✍ Yusheng Li; Cecil C. Rousseau; Ľubomír Šoltés 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 342 KB

The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V~, 112 ..... Va such that for each i at most d vertices in V~ U... U V, have neighbors in V~+~ and r(Kk, (Vi))<~ pIV(G) I, where (V i) denotes the