R(W5 , K5) = 27

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from http://ritdml.rit.edu/handle/1850/2759 to RIT Scholar Works http://scholarworks.rit.edu/theses/6897, please update your feeds & links!
Title: R(W5 , K5) = 27
Author: Stinehour, Joshua
Abstract: The two-color Ramsey number R(G , H) is defined to be the smallest integer n such that any graph F on n vertices contains either a subgraph isomorphic to G or the complement of F contains a subgraph isomorphic to H. Ramsey numbers serve to quantify many of the existing theorems of Ramsey theory, which looks at large combinatorial objects for certain given smaller combinatorial objects that must be present. In 1989 George R. T. Hendry presented a table of two-color Ramsey numbers R(G , H) for all pairs of graphs G and H having at most five vertices. This table left seven unsolved cases, of which three have since been solved. This thesis eliminates one of the remaining four cases, R(W5 , K5), where a K5 is the complete graph on five vertices and a W5 is a wheel of order 5, which can be pictured as a wheel having four spokes or as a cycle of length 4 having all four vertices adjacent to a central vertex. In this thesis we show R(W5, K5) to be equal to 27, utilizing a combinatorial approach with significant computations. Specifically we use a technique developed by McKay and Radziszowski to effectively glue together smaller graphs in an effort to prove exhaustively that no graph having 27 vertices exists that does not contain an independent set on five vertices or a subgraph isomorphic to W5. The previous best bounds for this case were 27 <= R( W_5 , K_5 ) <= 29.
Record URI: http://hdl.handle.net/1850/2759
Date: 2006

Files in this item

Files Size Format View
JStinehourMasterProject2003.pdf 1.028Mb PDF View/Open
JStinehourProposal2003.pdf 111.2Kb 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