The Ramsey number R(o, alpha) is the minimum number n such that every graph G with |V(G)| ≥ n has an induced subgraph that is isomorphic to a complete graph on o vertices, Ko, or has an independent set of size alpha, Nalpha. Graphs having fewer than n vertices that have no induced subgraph isomorphic to K o or Nalpha form a class of Ramsey graphs, denoted reals(o, alpha). This dissertation establishes common structure among several classes of Ramsey graphs and establishes the complete list of reals(3, 4).;The process used to find the complete list for reals(3, 4) can be extended to find other Ramsey numbers and Ramsey graphs. The technique for finding a complete list for reals(o, alpha), a) is inductive on n vertices in that a complete list of all graphs in reals(o, alpha) having exactly n vertices can be used to find the complete list n + 1 vertices. This process can be repeated until any extension is not in reals(o, alpha), and thus R(o, alpha) has been determined. We conclude by showing how to extend methods presented in proving R(3, 4) in finding R(5, 5).
展开▼
