On Saturation Spectrum Público
Fuller, Jessica Marie (2017)
Abstract
Given a graph H, we say a graph G is H-saturated if G does not contain H as a subgraph and the addition of any edge not already in G results in H as a subgraph. The question of the minimum number of edges of an H saturated graph on n vertices, known as the saturation number, and the question of the maximum number of edges possible of an H -saturated graph, known as the Turan number, has been addressed for many different types of graphs. We are interested in the existence of H -saturated graphs for each edge count between the saturation number and the Turan number.
We determine the saturation spectrum of (Kt-e)-saturated graphs and Ft-saturated graphs. Let (Kt-e) be the complete graph minus one edge. We prove that (Kt-e)-saturated graphs do not exist for small edge counts and construct (Kt-e)-saturated graphs with edge counts in a continuous interval. We then extend the constructed (Kt-e)-saturated graphs to create (Kt-e)-saturated graphs.
Let Ft be the graph consisting of t edge-disjoint triangles that intersect at a single vertex v. We prove that F2-saturated graphs do not exist for small edge counts and construct a collection of F2-saturated graphs with edge counts in a continuous interval. We also establish more general constructions that yield a collection of Ft-saturated graphs with edge counts in a continuous interval.
Table of Contents
- Introduction
- On the Saturation Spectrum of (Kt-e)-saturated graphs
- On the Saturation Spectrum of Ft-saturated graphs
- Future Work
Bibliography
About this Dissertation
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Palavra-chave | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
On Saturation Spectrum () | 2018-08-28 15:44:44 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
coverPage.tex () | 2018-08-28 15:45:18 -0400 |
|
|
approvalSheet.tex () | 2018-08-28 15:45:23 -0400 |
|
|
customCommands.tex () | 2018-08-28 15:45:31 -0400 |
|
|
emoryTemplate.tex () | 2018-08-28 15:45:37 -0400 |
|
|
distributionAgreement.tex () | 2018-08-28 15:45:44 -0400 |
|
|
Tnp.png () | 2018-08-28 15:45:50 -0400 |
|
|
figures.tex () | 2018-08-28 15:45:54 -0400 |
|
|
theoremStyle.tex () | 2018-08-28 15:46:17 -0400 |
|
|
abstractCoverPage.tex () | 2018-08-28 15:46:43 -0400 |
|
|
acknowledgments.tex () | 2018-08-28 15:46:53 -0400 |
|
|
abstract.tex () | 2018-08-28 15:47:01 -0400 |
|