You are here
ON SATURATION NUMBERS OF RAMSEYMINIMAL GRAPHS
 Date Issued:
 2018
 Abstract/Description:
 Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring of G, we say c is a bad coloring if G contains no red K3or blue K1,t under c. A graph G is (H1,...,Hk)Ramseyminimal if G arrows (H1,...,Hk) but no proper subgraph of G has this property. Given a family F of graphs, we say that a graph G is Fsaturated if no member of F is a subgraph of G, but for any edge xy not in E(G), G + xy contains a member of F as a subgraph. Letting Rmin(K3, K1,t) be the family of (K3,K1,t)Ramsey minimal graphs, we study the saturation number, denoted sat(n,Rmin(K3,K1,t)), which is the minimum number of edges among all Rmin(K3,K1,t)saturated graphs on n vertices. We believe the methods and constructions developed in this thesis will be useful in studying the saturation numbers of (K4,K1,t)saturated graphs.
Title:  ON SATURATION NUMBERS OF RAMSEYMINIMAL GRAPHS. 
39 views
22 downloads 

Name(s): 
Davenport, Hunter M, Author Song, ZiXia, Committee Chair University of Central Florida, Degree Grantor 

Type of Resource:  text  
Date Issued:  2018  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring of G, we say c is a bad coloring if G contains no red K3or blue K1,t under c. A graph G is (H1,...,Hk)Ramseyminimal if G arrows (H1,...,Hk) but no proper subgraph of G has this property. Given a family F of graphs, we say that a graph G is Fsaturated if no member of F is a subgraph of G, but for any edge xy not in E(G), G + xy contains a member of F as a subgraph. Letting Rmin(K3, K1,t) be the family of (K3,K1,t)Ramsey minimal graphs, we study the saturation number, denoted sat(n,Rmin(K3,K1,t)), which is the minimum number of edges among all Rmin(K3,K1,t)saturated graphs on n vertices. We believe the methods and constructions developed in this thesis will be useful in studying the saturation numbers of (K4,K1,t)saturated graphs.  
Identifier:  CFH2000291 (IID), ucf:45881 (fedora)  
Note(s): 
20180501 B.S. College of Sciences, Mathematics Bachelors This record was generated from author submitted information. 

Subject(s): 
edgecoloring saturated graphs ramsey theory ramseyminimal 

Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFH2000291  
Restrictions on Access:  public  
Host Institution:  UCF 