On Saturation Spectrum Open Access

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

1. Introduction
2. On the Saturation Spectrum of (Kt-e)-saturated graphs
3. On the Saturation Spectrum of Ft-saturated graphs
4. Future Work

Bibliography

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Mathematics
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Mathematics
Keyword	Graph Theory Saturation spectrum
Committee Chair / Thesis Advisor	Gould, Ronald J, Emory University
Committee Members	Rodl, Vojtech, Emory University Duffus, Dwight A, Emory University Huang, Hao , Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	On Saturation Spectrum ()	2018-08-28 15:44:44 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions
	coverPage.tex ()	2018-08-28 15:45:18 -0400	Press to Select an action Download
	approvalSheet.tex ()	2018-08-28 15:45:23 -0400	Press to Select an action Download
	customCommands.tex ()	2018-08-28 15:45:31 -0400	Press to Select an action Download
	emoryTemplate.tex ()	2018-08-28 15:45:37 -0400	Press to Select an action Download
	distributionAgreement.tex ()	2018-08-28 15:45:44 -0400	Press to Select an action Download
	Tnp.png ()	2018-08-28 15:45:50 -0400	Press to Select an action Download
	figures.tex ()	2018-08-28 15:45:54 -0400	Press to Select an action Download
	theoremStyle.tex ()	2018-08-28 15:46:17 -0400	Press to Select an action Download
	abstractCoverPage.tex ()	2018-08-28 15:46:43 -0400	Press to Select an action Download
	acknowledgments.tex ()	2018-08-28 15:46:53 -0400	Press to Select an action Download
	abstract.tex ()	2018-08-28 15:47:01 -0400	Press to Select an action Download