Premium
Ramsey unsaturated and saturated graphs
Author(s) -
Balister P.,
Lehel J.,
Schelp R.H.
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20118
Subject(s) - ramsey's theorem , combinatorics , mathematics , epigraph , graph , discrete mathematics , mathematical optimization
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.