On Kt-saturated Graphs Público
Amin, Kinnari Vaibhavkumar (2010)
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
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Palavra-chave | |
Committee Chair / Thesis Advisor | |
Committee Members |
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 |
|