On (3, k) Ramsey graphs: Theoretical and computational results

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from http://ritdml.rit.edu/handle/1850/9811 to RIT Scholar Works http://scholarworks.rit.edu/article/640, please update your feeds & links!
Title: On (3, k) Ramsey graphs: Theoretical and computational results
Author: Radziszowski, Stanislaw; Kreher, Donald
Abstract: A (3,k,n,e) Ramsey graph is a triangle-free graph on n vertices with e edges and no independent set of size k. Similarly, a (3,k)-, (3,k,n)- or (3,k,n,e)-graph is a (3,k,n,e) Ramsey graph for some nand e. In the first part of the paper we derive an explicit formula for the minimum number of edges in any (3,k,n)graph for n ≤ 3(k-I), i.e. a partial formula for the function e(3,k,n) investigated in [3,5,7]. We prove some general properties of minimum (3,k,n)- graphs with e(3,k,n) edges and present a construction of minimum (3,k+I,3k-I,5k-5)-graphs for k ≥ 2 and minimum (3,k+1,3k,5k)-graphs for k ≥ 4. In the second part of the paper we describe a catalogue of small Ramsey graphs: all (3,k)-graphs for k ~6 and some (3,7)-graphs including all 191 (3,7,22)-graphs, produced by a computer. We present for k ≤ 7 all minimum (3,k,n)-graphs and all 10 maximum (3,7,22)-graphs with 66 edges. *Please refer to full-text for correct equations and numerical values
Record URI: http://hdl.handle.net/1850/9811
Date: 1988

Files in this item

Files Size Format View
SRadziszowskiArticle10-1988.pdf 5.822Mb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML

Advanced Search