On Kt-saturated Graphs Open Access

Amin, Kinnari Vaibhavkumar (2010)

Permanent URL: https://etd.library.emory.edu/concern/etds/rx913q376?locale=en
Published

Abstract

Let G be a graph on n vertices. Let H be a graph. Any H-free graph G is called H-saturated if the addition of any edge e ∉ E(G) results in H as a subgraph of G. The minimum size of an H-saturated graph on n vertices is called a saturation number, denoted by sat(n, H). The edge spectrum for the family of graphs with property P is the set of all sizes of graphs with property P.

In this dissertation, we show the edge spectrum of K4-saturated graphs. We also classify all K4-saturated graphs of connectivity 2 and 3. Furthermore, we show that, for n ≥ 5t − 7, there is an (n, m) Kt-saturated graph G if and only if G is complete (t − 1)-partite graph or (t − 1)(n − (t⁄2)) − 2 ≤ m ≤ ⌊ [(t−2)n2−2n+(t−2)]⁄[2(t−1)]⌋ + 1.

Table of Contents

Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2

1.2 Extremal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

1.3 Saturation Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . .6

2 K4-Saturated Graphs . . . . . . . . . . . . . . . . . . . . . . . 12

2.1 Results on K4-saturated Graphs . . . . . . . . . . . . . . 13

2.2 Hanson and Toft Result . . . . . . . . . . . . . . . . . . . . . . . 22

2.3 The Edge Spectrum of K4-saturated Graphs . . . . . .24

3 Kt-Saturated Graphs . . . . . . . . . . . . . . . . . . . . . . . .27

3.1 Lower Bound for Kt-saturated Graphs . . . . . . . . . . 28

3.2 Upper Bound for Kt-saturated Graphs . . . . . . . . . . 48

3.3 Edge Spectrum of Kt-saturated Graphs . . . . . . . . .49

4 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

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
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Thumbnail Title Date Uploaded Actions
On Kt-saturated Graphs () 2018-08-28 14:06:36 -0400

Supplemental Files

Thumbnail Title Date Uploaded Actions
figure1.eps () 2018-08-28 14:07:08 -0400
chapter4.tex () 2018-08-28 14:07:17 -0400
figure_5.eps () 2018-08-28 14:07:22 -0400
ex1.eps () 2018-08-28 14:07:29 -0400
ex3.eps () 2018-08-28 14:07:36 -0400
mybib.tex () 2018-08-28 14:07:50 -0400
figure3.eps () 2018-08-28 14:08:14 -0400
figure6.eps () 2018-08-28 14:08:47 -0400
mydata.tex () 2018-08-28 14:09:11 -0400
figure_3.eps () 2018-08-28 14:09:18 -0400
figure_1.eps () 2018-08-28 14:09:23 -0400
mythesis.tex () 2018-08-28 14:09:28 -0400
introduction.tex () 2018-08-28 14:09:32 -0400
figure8.eps () 2018-08-28 14:09:36 -0400
chapter2.tex () 2018-08-28 14:09:44 -0400
preamble.tex () 2018-08-28 14:09:51 -0400
graph.eps () 2018-08-28 14:09:59 -0400
ex2.eps () 2018-08-28 14:10:06 -0400
figure9.eps () 2018-08-28 14:10:13 -0400
chapter3.tex () 2018-08-28 14:10:20 -0400
figure_4.eps () 2018-08-28 14:10:26 -0400
turang.eps () 2018-08-28 14:10:32 -0400