R(W5 , K5) = 27

Show simple item record

dc.contributor.advisor Radziszowski, Stanislaw - Chair en_US
dc.contributor.advisor Hemaspaandra, Edith en_US
dc.contributor.advisor Tse, Kung-Kuen en_US
dc.contributor.author Stinehour, Joshua
dc.date.accessioned 2006-11-14T15:26:30Z
dc.date.available 2006-11-14T15:26:30Z en_US
dc.date.issued 2006
dc.identifier.uri http://hdl.handle.net/1850/2759
dc.description.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.
dc.format.extent 1028095 bytes en_US
dc.format.extent 111285 bytes en_US
dc.format.mimetype application/pdf en_US
dc.format.mimetype application/pdf en_US
dc.language.iso en_US
dc.subject Graph coloring en_US
dc.subject Ramsey numbers en_US
dc.subject.lcsh QA166 .S75 2004
dc.subject.lcsh Ramsey numbers
dc.subject.lcsh Ramsey theory
dc.subject.lcsh Graph theory
dc.subject.lcsh Combinatorial analysis
dc.title R(W5 , K5) = 27
dc.type Masters Project
dc.description.defense 38103
dc.description.college B. Thomas Golisano College of Computing and Information Sciences
dc.description.department Department of Computer Science
dc.description.approval 38103

Files in this item

Files Size Format View
JStinehourMasterProject2003.pdf 1.028Mb PDF View/Open
JStinehourProposal2003.pdf 111.2Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search RIT DML


Advanced Search

Browse