You are here

UCF Digital Collections ยป Honors Collection

ON SATURATION NUMBERS OF RAMSEY-MINIMAL GRAPHS

Download pdf | Full Screen View

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 edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every k-edge-coloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring 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)-Ramsey-minimal 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 F-saturated 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 RAMSEY-MINIMAL GRAPHS.
39 views
22 downloads
Name(s): Davenport, Hunter M, Author
Song, Zi-Xia, 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 edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every k-edge-coloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring 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)-Ramsey-minimal 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 F-saturated 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): 2018-05-01
B.S.
College of Sciences, Mathematics
Bachelors
This record was generated from author submitted information.
Subject(s): edge-coloring
saturated graphs
ramsey theory
ramsey-minimal
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFH2000291
Restrictions on Access: public
Host Institution: UCF

In Collections