Minimum triangle-free graphs

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from to RIT Scholar Works, please update your feeds & links!
Title: Minimum triangle-free graphs
Author: Radziszowski, Stanislaw; Kreher, Donald
Abstract: We prove that e(3, k + 1, n) >= 6n - 13k where e(3, k + 1, n) is the minimum number of edges in any triangle-free graph on n vertices with no independent set of size k + 1. to achieve this we first characterize all such graphs with exactly e(3, k + 1, n) edges for n <= 3k. These results yield some sharp lower bounds for the independence ratio for trianagle-free graphs. In particular, the exact value of the minimal independence ratio for graphs with average degree 4 is shown in be 4/13. A slight improvement to the general upper bound for the classical Ramsey R(3,k) numbers is also obtained.
Record URI:
Date: 1991

Files in this item

Files Size Format View
SRadziszowskiArticle06-1991.pdf 3.380Mb 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