The Ramsey numbers R(K_4-e, K_6-e) and R(K_4-e,K_7-e)

Show full item record

Title: The Ramsey numbers R(K_4-e, K_6-e) and R(K_4-e,K_7-e)
Author: McNamara, James; Radziszowski, Stanislaw
Abstract: The graph with vertices in GF(16), whose edges connect points having difference equal to a cube, which was known to be extremal for the Ramsey numbers R(3,3,3) and R(K_3, K_6-e), is shown to be extremal for R(K_4-e, K_6-e). The proof is obtained by using computer algorithms to analyze the properties of the family of graphs having no K_4-e and having no K_5-e in the complement. It is also shown that there is a unique graph, up to graph isomorphism, which is extremal for R(K_4-e, K_7-e), viz., the strongly regular Schlafli graph on 27 vertices, which has an automorphism group of size 51840. This follows easily from the result that R(K_4-e, K_6-e) is 17.
Record URI: http://hdl.handle.net/1850/8771
Date: 1991

Files in this item

Files Size Format View
SRadziszowskiArticle12-1991.pdf 991.1Kb 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

Browse