On Saturation Spectrum Público

Fuller, Jessica Marie (2017)

Permanent URL: https://etd.library.emory.edu/concern/etds/b5644s522?locale=pt-BR
Published

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
Department
Degree
Submission
Language
  • English
Research Field
Palavra-chave
Committee Chair / Thesis Advisor
Committee Members
Última modificação

Primary PDF

Supplemental Files