SATURATION SPECTRUM FOR TREES
by
BRENT J. THOMAS
B.S., Utah State University, 2007
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
2016
This thesis for the Doctor of Philosophy degree by
Brent J. Thomas
has been approved for the
Department of Mathematical and Statistical Sciences
by
Michael S. Jacobson, Advisor
Michael J. Ferrara, Chair
David Brown
Jill Faudree
Florian Pfender
April 29, 2016
11
Thomas, Brent J. (Ph.D., Applied Mathematics)
Saturation Spectrum for Trees
Thesis directed by Professor Michael S. Jacobson
ABSTRACT
Graph saturation is a wellstudied area of extremal graph theory. A graph G is H
saturated if H is not a subgraph of G but the addition of any edge from G to G results
in a copy of H. The number of edges in a graph G is called the size of G. The minimum
size of an iJsaturated graph on n vertices is called the saturation number for H and is
denoted sat(n, iJ); the maximum size is the extremal number, ex(n, H). Historically,
the primary focus of the study of graph saturation was aimed at understanding the
structure of iJsaturated graphs with sizes close to the thresholds, sat(n,H) and
ex(n, H), with the ultimate goal of determining these values.
The main focus of this thesis is to study the structure of iJsaturated graphs, the
properties they have, and ultimately to determine the number of edges contained in
iJsaturated graphs for a variety of particular graph families. Results are primarily
focused on an assortment of trees. The saturation spectrum for a graph H, which is
denoted spec(n, H), is the set of sizes of iJsaturated graphs between sat(n, H) and
ex(n, H). It will be shown that the saturation spectrum for stars is complete, that is,
it contains every integer between sat(n, H) and ex(n, H). Additionally, we prove that
the saturation spectrum for a path contains every integer from sat(n, H) to within a
constant, which depends on k, of ex(n, H)\ we also prove a similar result for brooms.
Additionally, we determine completely the saturation spectrum for a number of small
brooms and show that for a general family of brooms there are integers immediately
preceding the extremal number that are not in the saturation spectrum.
Finally, for large families of trees we give a bound on the maximum average
iii
degree of a connected Hsaturated graph that is not a complete graph. One of the
consequences of this bound is that the saturation spectrum has a gap immediately
preceding ex.{n,H). The proof used to give this bound and hence the gap in the
saturation spectrum is not dependent on the structure of the tree, hence the proof
establishes a general technique that could be applied to a broad families of trees.
The form and content of this abstract are approved. I recommend its publication.
Approved: Michael S. Jacobson
IV
DEDICATION
To my wife Jessica, for her love and support.
v
ACKNOWLEDGMENT
My time at the University of Colorado Denver has been some of the most rewarding
and challenging of my life. I owe thanks to many people for helping me along the
way.
First I would like to thank the graduate committee and the department for pro
viding me with teaching assistantships and honoring me with awards, including the
Lynn Bateman Teaching Award and the Lynn Bateman Fellowship.
I am also grateful to many faculty members for their mentoring and support. In
particular, I am grateful for the guidance and assistance provided by Mike Ferrara
and Florian Pfender, who both played a big role in helping me stay on track while
my advisor Mike Jacobson spent two years at the NSF. Additionally, I thankful to
David Brown, Jill Faudree, Michael Ferrara, Michael Jacobson, and Florian Pfender,
for serving on my Ph.D. committee and helping me improve the quality of this thesis.
I know much of what I have accomplished at CU Denver would not have been
possible without the other graduate students. The graph theory students, in partic
ular, have made my time at CU Denver much more enjoyable and productive. I owe
a special thanks to Axel Brandt for sharing an office with me and showing me that
it is always possible to work a little harder.
Finally, I would like to thank my advisor Michael Jacobson. In addition to teach
ing me how to become a successful mathematical researcher and educator, he has
helped me balance the demands of family and life with school. I know that to a great
extent, I indebted to him for my positive experiences at CU Denver.
vi
TABLE OF CONTENTS
Tables...................................................................... viii
Figures ...................................................................... ix
Chapter
1. Introduction and Notation.................................................. 1
1.1 Definitions and Notation............................................. 1
1.2 Prologue............................................................. 4
2. Overview of Saturation...................................................... 6
2.1 Extremal Numbers..................................................... 6
2.2 Saturation Numbers................................................. 11
2.3 Saturation Spectrum ............................................... 24
3. Saturation Spectrum of Stars and Paths ................................... 26
3.1 Stars............................................................... 26
3.2 Paths............................................................... 32
4. Saturation Spectrum of Brooms.............................................. 37
4.1 Saturation for BSyt................................................ 37
4.2 Saturation Spectrum for Bs>t..................................... 40
4.3 Saturation Spectrum of B3>t........................................ 44
4.3.1 Saturation Spectrum of B32................................... 51
4.3.2 Saturation Spectrum of B3>3.................................. 54
5. Gaps in the Saturation Spectrum............................................ 57
6. Future Work................................................................ 65
References.................................................................... 68
vii
TABLES
Table
4.1 Saturation Spectrum of Â£>3,2 for 5 < n < 11............................ 52
4.2 Saturation Spectrum of Â£>3,3 for 17 < n < 21........................... 56
viii
FIGURES
Figure
11 ^2,2,2 3
2.1 3P3saturated graphs...................................................... 20
2.2 Sage Code Used to Find SAT(9,3P3)......................................... 21
3.1 Type I exchange........................................................... 27
3.2 Type II exchange.......................................................... 27
3.3 T515...................................................................... 33
4.1 Some B3>t saturated graphs................................................ 46
IX
CHAPTER 1
INTRODUCTION AND NOTATION
1.1 Definitions and Notation
We begin by providing rigorous definitions for some of the basic concepts that
will be studied in the chapters that follow.
A graph G is an ordered pair (V, E) of sets. The set V(G) is called the vertex set
and the second set, of two element subsets of V(G), E(G) is the edge set. Elements
of V(G) (respectively E(G)) are called vertices (respectively edges). We write v E G
(e G G) to denote v E V(G) (e G E(G)). When the context is clear we will abbreviate
V(G) and E(G) by V and E, respectively. The order of a graph is U(G), which
will often be shortened to G and the size of a graph is if(G), which will frequently
be written e(G). Two vertices u,v E V(G) are said to be adjacent if {u,v} E E(G).
It will be useful to denote that u and v are adjacent by u ~ v and that u and v are
nonadjacent by u oo v. For brevity, {u,v} E E(G) is usually denoted by uv E E(G)
or uv if the context is clear. The complement of a graph G denoted G is a graph with
vertex set V(G) and u ~ v in G if and only if u oo v in G.
The neighborhood of a vertex u in a graph G is the set {v E V(G) : u ~ v} and
will be denoted by Ng(u). The closed neighborhood of u in G is the set iV(tt)U{tt} and
will be denoted by NG[u], If the context is clear NG(u) and NG[u] may be abbreviated
by N(u) and N[u] respectively. The degree of a vertex u in a graph G, denoted d(u),
is ArG(t(). The minim,um, (maximum) degree of a graph G is min(max){h(t() : u E
V(G)}. Notationally, we use 8(G) to represent the minimum degree of G and A(G)
to represent the maximum degree. The average degree of G, that is j^J2veGd(v),
and will be denoted by d(G).
An isomorphism from a graph G to a graph H is a bijection V(G) > V(H) such
that uv E E(G) if and only if f(u)f(v) E E(H). G = H will be used to denote that
1
G is isomorphic to H. The isomorphism relation is an equivalence relation on the
set of graphs, thus generally if we do not specify a set of vertices when we refer to
a graph we are referring to the equivalence class, also called an isomorphism class,
which contains that graph under the isomorphism relation.
A subgraph, H, of a graph G is a graph such that V(H) C V(G) and E(H) C
E(G). The property H is a subgraph of G is often described by saying G contains
H and denoted by H C G. If H is not contained in G then we say that G is Hfree.
H is an induced subgraph of G if H is a subgraph of G and whenever u,v E V(H) and
uv E E(G), then uv E E(H). A subgraph induced by a set of vertices, X C V(G),
will be denoted by G[X],
The complete graph of order n, denoted Kn, is a graph with every pair of vertices
adjacent. A complete subgraph of a graph is sometime referred to as a clique. A set
of vertices with no edges between them is called an independent set.
A path of order n, denoted Pn, is a graph whose vertices can be ordered so that
two vertices are adjacent if and only if they appear consecutively in the order. The
distance between two vertices, u and v, is the length of the shortest path having u and
v as endpoints. The distance will be denoted d(u,v). When there is no path between
u and v we say d(u,v) = oo and when u ~ v it follows that d(u,v) = 1. A cycle of
order n is a sequence of vertices, V\, u2,..., vn, so that Vi ~ vi+\, 1 < i < n 1, and
vn ~ V\. If every vertex in the graph induced by the vertices of cycle has degree 2
then the graph is called a cycle and denoted Cn. A graph is connected if there is path
between any two vertices of the graph. A graph that contains no cycles is called a
forest, a connected forest is a tree. A maximal connected set of vertices of a graph is
called a component. If the graph is connected there is a single component.
A bipartite graph is a graph whose vertex set can be partitioned into two indepen
dent sets. Specifically, if G is a bipartite graph then V(G) = X U Y with X n Y = 0
such that whenever u ~ v in G exactly one of u or v is in X. The sets X and Y are
2
Figure 1.1: K2,2,2
often called partite sets. The complete bipartite graph, denoted Kn>m, is a bipartite
graph where the partite sets have size n and m and u ~ v whenever u E X and v eY.
More generally a kpartite graph is a graph whose vertex set can be partitioned into
k independent sets. A complete fcpartite graph, denoted idTOl)TO2)...)TOfc, induces a par
tition of V(G) into k independent sets V\, v2, to that if x E ry and y E Vj, for
i ^ j, then xy E E{Kmi>m2>^>mk). For example, K2>2>2 is the complete 3 partite
graph having each partite set of order 2 (see Figure 1.1).
A graph G is said to be Hsaturated if G is Hfree but G + e contains H for
every edge e such that e G E(G). The set of all //saturated graphs of order n
is denoted by SAT(n,H). The set of graphs of minimum size in SAT(n,H) is
denoted by SAT(n, H). Similarly the set of graphs of maximum size in SAT(n, H)
is denoted by SAT(n, H). The saturation number of a graph E[ is size of G such that
G E SATfa, H) and will be denoted by sat(n,H). Similarly the extremal number
of a graph E[ is is the size of G such that G E SAT(n, H) and will be denoted by
ex(n, H). The saturation spectrum, of a graph H, denoted spec(n,H), is the set of
sizes of Hsaturated graphs of order n, spec(n,H) = {e(G) : G E SAT(n,H)}. If
there is an integer m such that m spec(n, H), we say there is a gap in the saturation
spectrum for H.
The definitions above can be generalized by replacing the graph Et with a family
of graphs T. So, a graph G is ^'saturated if G contains no member of T as a
subgraph but for every edge e E G, there exists F E T such that G + e contains F
as a subgraph.
3
1.2 Prologue
The work of Mantel [34] in 1907 and Turan [39] in 1941 laid the foundation
for the study of graph saturation. The structure of //saturated graphs has been
studied with with goal to minimize or maximize the number of edges in the graph.
In addition, the concept of saturation has been extended beyond graphs to other
combinatorial structures including hypergraphs and directed graphs. One of the more
recent directions in the study of graph saturation is determining all possible sizes of
//saturated graphs.
In Chapter 2 we present a brief history of results related to graph saturation, in
cluding concepts and results pertaining to //saturated graphs with the minimum and
maximum number of edges. Of particular interest to the principle work in this thesis
will be results pertaining to trees and linear forests. Our initial work in this chapter
will also include some improvements to known work on saturation of linear forests.
Finally, some of the known results on the saturation spectrum will be presented, with
particular emphasis on complete graphs and small paths.
In Chapter 3, results regarding the saturation spectrum for stars and paths
will be given. We will build on the work of Erdos and Gallai [17] who deter
mined the maximum size of a pathsaturated graph and Kaszonyi and Tuza [28]
who gave the minimum size of a pathsaturated graph, along with a characteriza
tion of starsaturated graphs. We prove that the saturation spectrum of stars is
complete. That is, it contains all sizes between the saturation number and the ex
tremal number. We also show that the saturation spectrum of contains all sizes m
for sat(n, Pk) < m < ex(n, Pk) c{k).
A broom is a tree constructed by associating the endpoint of a path with the
center vertex of a star. In Chapter 4, we build upon the results in Chapter 3 by
considering the saturation spectrum of brooms. Unlike paths and stars the sat(n,B)
is unknown, where B is a broom, except for a few specific brooms. Lemma 4.1 gives
4
a construction that establishes an upper bound on the minimum size of a broom
saturated graph. We then prove that the saturation spectrum is continuous from
that bound to within a constant, which depends on the order of the broom, of the
conjectured extremal number for brooms. We then study the saturation spectrum
of specific brooms, in particular brooms that can be obtained by identifying an end
vertex of P3 with the center of an arbitrary star. In this case, when the star has either
3 or 4 vertices the saturation spectrum is completely determined. In general, when
the star has at least 3 vertices we show that there is a gap in the saturation spectrum
near the extremal number.
In Chapter 5, we consider a more general question of determining, for large fam
ilies of general trees, when there is a gap in the saturation spectrum. We give condi
tions that ensure there is a gap in the saturation spectrum for large families of trees
and use this technique to show that there is a gap in the saturation spectrum of paths
as well as trees containing a vertex adjacent to a large number of leaves.
5
CHAPTER 2
OVERVIEW OF SATURATION
In this chapter, we will give an overview of graph saturation results. Of particular
interest will be results on the saturation number and extremal numbers for trees.
2.1 Extremal Numbers
The first result in the area of graph saturation is due to Mantel and and an
unattributed group of his students.
Theorem 2.1 (Mantel [34])
ex(n, K3)
n
T
It is easy to see that every complete bipartite graph is id3saturated and when
2
the partite sets are as close in size as possible the complete bipartite graph has Pl
edges. Turan generalized the work of Mantel by determining the extremal number
for all complete graphs. Let TUyP denote the complete balanced (the sizes of any two
partite sets differ by at most one) ppartite graph on n vertices.
Theorem 2.2 (Turan [39])
TUyP is the unique Kp+1 saturated graph of order n with ex(n, Ap+1) edges.
Let Kf be the complete multipartite graph Kniy_yna where n\ = = ns = p.
Turans Theorem guarantees that a every graph with order n and more than e(Tra>p_i)
edges contains a copy of Kp. It is somewhat surprising that, for any fixed e > 0 and
n large, just tv2 more edges gives not only a copy of Kp but a copy of Kf, a graph
with many copies of Kp.
6
Theorem 2.3 (Erdos and Stone [21])
For all integers p > 2 and s > 1, and every e > 0, there exists an integer no such that
every graph with n > no vertices and at least
e(TraiP_!) + en2
edges contains Kf.
Every subgraph of Tn>p is at most ppartite. Since a graph H with x(H) > p + 1
is at least p + 1partite, it follows that Tn>p is Hfree. Thus ex.(n,H) > e(Tn>p) =
(l ^ () + o(n2). A corollary of the Erdos and Stone theorem shows that this
bound is tight.
Theorem 2.4 (Erdos and Simonovits [19])
If H is a graph with at least one edge and x(H) = p + 1, then
ex(n, H) = ^1 ^ Q + o{n2).
In light of the previous theorem, the authors of [26] point out that ex(n, H)
depends mostly on x(H); up to an error term of order o(n2). Based on this result, it
is natural to ask if the structure of Hfree graphs with size close to ex(n, H) is also
almost completely determined by x(H). If so, each such graph would be very similar
to TUtP. Erdos and Simonovits [15, 16, 38] show the answer is yes.
Theorem 2.5 (Erdos and Simonovits [19, 16, 38] )
Let H be a graph with x(H) = p + 1. For every e > 0, there exists a 8 > 0 and n
such that for n > ne, if G is a graph of order n that is Hfree and
e(G) > ex(n, H) 8n2,
then G can be obtained from, TUtP by deleting and adding at most en2 edges.
7
The previous three theorems show how the extremal number for H and the struc
ture of graphs in SAT(n,H) depend strongly on y(i7) when y(i7) > 3. When
x(H) = 2, less is known about ex(n, H) and the structure of graphs in SAT(n, H).
In this case the ErdosStone Theorem only states that ex(n, H) = o(n2). However,
there are several results showing that with adequate understanding of the extremal
graphs for bipartite graphs, one can reduce the problem of determining the extremal
graphs for for nonbipartite graphs, to the bipartite case [26]. In particular, [20]
shows that determining the extremal graphs for complete (p + l)partite graphs can
be reduced to the problem of finding the extremal graphs of some particular complete
bipartite graphs.
There are many theorems on determining the extremal number of bipartite
graphs. We state some of these theorems below. A more comprehensive treatment of
results relating to the extremal numbers for bipartite graphs is contained in [26].
Theorem 2.6 (Kovari, Sos, and Turan [31])
ex(n,Kap) < ^
Theorem 2.7 ([29, 4])
Ifb>(a 1)!, then
ex(n, Ka>b) > can2~{1/a).
Theorem 2.8 (Bondy and Simonovits [9])
ex(n, C2k) < 100kn1+^bk\
For the purposes of this thesis, we are particularly interested
numbers for trees. It is a straightforward exercise to show that ex(n,
In 1959, Erdos and Gallai [17] gave bounds on the extremal number of paths.
in the extremal
Kip1) < ^n.
8
Theorem 2.9 (Erdos and Gallai [17])
If k > 2 then
ex(n, Pk) < n
with equality if and only if k 1 divides n and all connected components of G are
complete graphs on k 1 vertices.
Consider the nvertex graph G that is the union of n/(k 1)J vertex disjoint
copies of Kki and a Kr (0 < r < k 2). It in not difficult to see that G does not
contain any tree with k vertices. It follows that
ex n.Ij, > nk .
\ kj  2 8
This fact together with the upper bounds on the extremal numbers for paths and
stars in part motivated the following conjecture of Erdos and Sos.
Conjecture 2.10 (Erdos and Sos [14])
Let Tk be an arbitrarily fixed kvertex tree. If a graph G is Tkfree, then
e(G) < ^(k 2)n.
From Theorem 2.9 and the discussion immediately proceeding the statement of
the theorem, it follows that Conjecture 2.10 holds when Tk is a path or a star. Various
other specific cases of the ErdosSos Conjecture have been proved.
Theorem 2.11 (Sidorenko [37])
If Tk has a vertex x connected to at least kj2 leaves, then the ErdosSos Conjecture
holds for this Tk.
Theorem 2.12 (McLennan [35])
If the diam,eter ofTk is at most 4, then the ErdosSos Conjecture holds for this Tk
9
Ajtai, Komlos, Simonovits, and Szemeredi have announced a proof of Conjecture
2.10 when k is large. They have stated that the proof will appear in a series of three
papers [1, 2, 3]. An outline of the proof appears in [26].
Theorem 2.13 (Ajtai et al. [1, 2, 3])
There exists an interger k0 such that if k > k0 and Tk is an arbitrarily large kvertex
tree, and the graph G is Tkfree, then
e(G) < ^(k 2)n.
Faudree and Schelp found the exact extremal number for paths.
Theorem 2.14 (Faudree and Schelp [24] and independently Kopylov [30])
Let n = r (mod k 1), 0 < r < k 2, k > 2. Then
. k 2 r(k 1 r)
ex(n, Pk) = n.
Extremal numbers of linear forests have also been studied. A forest where every
component is a path will be referred to as a linear forest.
Theorem 2.15 (Lidicky, Liu, and Palmer [32])
Let F be a linear forest with components of order V\, u2,..., vk. If at least one Vi is
not 3, then for n sufficiently large,
ex(n, F) = l
,i= 1
V.
2 J
k
111 n y,
i= 1
V,
2 J
+ 1 +
Ef, Lf J 1
where c = 1 if all Vi are odd and c = 0 otherwise. Moreover, the extremal graph is
unique.
Further, Lidicky et al. show that the unique extremal graph for a linear forest F
can be obtained from a complete bipartite graph G with partite sets A and B where
10
A = {^2ki=i\_Vi/^\^ 1 by adding edges to A so that G[A] forms a clique. If each ry
is odd then a single edge is added to B.
Notice the above theorem does not apply to a linear forest where every component
is P3. The following theorem will include the case where every component of a linear
forest is P3 (note this case was originally proved in [10]) and shows that in general
such a forest behaves like a star forest.
Theorem 2.16 (Lidicky, Liu, and Palmer [32])
Let F = Uti S* be a star forest where di is the maximum degree of Sl and d\ > >
> dk For n sufficiently large,
ex(n, F) = max < (i l)(n i + 1) + ( ) +
1
2.2 Saturation Numbers
Erdos, Hajnal, and Moon [18] introduced the idea of a saturation number and
proved the following theorem.
Theorem 2.17 (Erdos, Hajnal, and Moon [18])
If 2 < p < n, then sat(n, Kp) = {jp 2){n p + 2) + (p~2) and SAT( n, Kp) contains
only one graph, Kp_2 + Kn_p+2.
In general, much less is known about the saturation numbers for graphs than the
extremal number for graphs. In 1986, Kaszonyi and Tuza [28] found the best known
general upper bound for sat(n,7r). To state their result, we first define
u = u{F) = min{V(F) a{F) 1 : F G F}
and
d = d(F) = min{\E(F')\ : F' C F C T is induced by S U x}
where S is an independent set in F of size \V(F) \ u 1 and x E V(F) \ S.
di 1
(n i + 1)
11
Theorem 2.18 (Kaszonyi and Tuza [28])
sat(n, T) < un + (d 1 )(n u)/2
Faudree, Faudree, and Schmitt explain several interesting attributes of this theo
rem and its proof in [23]. First, the proof hinges on two straightforward observations
about saturation numbers for families of graphs. Second, in many cases the up
per bound given by the proof is sharp; for example, the bound is sharp for complete
graphs. Third, the proof implicitly describes a construction for an //saturated graph.
This construction produces an //saturated graph of minimum size in some cases, such
as when H is a complete graph, however this is not the case in general. Finally, the
theorem implies that sat(n, T) = 0(n). Notice this differs from the extremal number
where ex(n,F) = 0(n2) (see [19]).
Extremal numbers have several monotonicity properties that do not hold in gen
eral for saturation numbers. The extremal function ex(n, F) is monotone with respect
to n and F while the saturation sat(n, F) function is not. In particular, for F' C F
and F' C F the following inequalities hold for every n.
ex(n, F')
ex(n,J7)
ex(n, T)
In [28], it is observed that, in general, ex can not be replaced by sat in any of the
above inequalities, and examples are provided to illustrate this observation. In order
to show that Inequality 2.1 does not hold for the sat function, let F' = K 1>m and F =
K\ m + e, where e joins two vertices of degree 1. Notice that sat(n, F) < n 1 since
K\,ni is Fsaturated. However Theorem 2.24 implies that sat(n, F') > sat(n, F) for
n sufficiently large. Note the previous example was given in [36].
12
In [22], it is shown that Inequality 2.1 also fails when F is a tree.
Lemma 2.19 (Faudree et al. [22])
For a given tree T', T' is the subtree of a tree T such that sat(n,T) < n.
Interestingly, Faudree et al. also show that every tree is a subtree of a tree with
large saturation number.
Lemma 2.20 (Faudree et al. [22])
For a given tree T', T' is the subtree of a tree T such that sat(n,T) > an for any
constant a and n sufficiently large.
In order to show that Inequality 2.2 does not hold for the sat function, let T =
{Ki;TO, Ki>m + e} and F' = {Ki>m + e}. Notice sat(n, F) = sat(n, Ki>m) > n 1, but
sat(n, F') < n 1.
Finally, to show Inequality 2.3 does not hold for the sat function, let F = P4. As
we will see in Theorem 2.26, sat(2fc 1, P4) = k + 1 > sat(2fc, P4) = k.
The authors of [23] opine that the failure to be monotone makes proving state
ments about sat(n,P) difficult. In particular, they argue that the failure to be
monotone may explain the scarcity of results for sat(n, J7), but makes the function
interesting to study.
The saturation numbers for a few families of graphs has been determined; we will
now give several results that are pertinent to the research presented in this disser
tation, we refer the reader to [23] for a more complete treatment.Faudree, Ferrara,
Gould, and Jacobson [25] generalize Theorem 2.17.
Theorem 2.21 (Faudree et al. [25])
Let t > 1, p > 3 and n > p(p + l)i p2 + 2p 6 be integers. Then
P 2 2^j + (p2)(np + 2).
Furthermore, if t = 2 or 3 then there is a unique graph in SATfa, tKp).
sat (n, tKp) = (t 1) r
p+ 1
2
13
Faudree et al. also found the saturation number for generalized friendship graphs.
For integers t, p, and Â£, define FttPg to be the graph composed of t copies of Kp
intersecting in a common Kg.
Theorem 2.22 (Faudree et al. [25])
Let t > 2, p > 3 and p 2 > Â£ > 1 be integers. Then, for sufficiently large n,
sat(n, Ft>p/) = (p 2)(n p + 2) + ^ ^ + (t 1) ^ ^ + ^ .
Bohman, Fonoberova, and Pikhurko [8] showed that saturation function for a
complete multipartite graph behaves asymptotically like the upperbound from The
orem 2.18.
Theorem 2.23 (Bohman et al. [8])
Let p > 2, sp > > Si > 1. Then for all large n,
sat(n, Kslt'">Sp) = + + sp_i 4 ^^ n + 0(n3^4).
We will now give an overview of results pertaining to saturation numbers for trees
and forests.
Theorem 2.24 (Kaszonyi and Tuza [28])
Let Sk = Kitk~i denote a star on k vertices. Then,
and
sat(n, Sk)
'rafc+l^
(fci)2"
8
if k < n <
if^
Kk1 U Kn_k+1 if
MI (n,Sk)= l
[G>UK[k/2\ if^
where G' is a (k 1)regular graph on n \_k/2\ vertices. Also note that in
the second case, (n > an edge is added between G' and K^k/2\, if k 1 and
14
n \_k/2\ are both odd. Furthermore, let T be a tree on k vertices such that T yt Sk,
then sat(n,T) < satin, Sk).
It is interesting to note that the previous theorem implies that among all trees of
order k, the star has the largest saturation number. In [22], Faudree et al. find the
tree with the smallest saturation number.
Theorem 2.25 (Faudree et al. [22])
For n > k + 2,
n + k 2
sat(n, D3)fc_3) = n 
and SAT(n, Â£>3;fc_3) consists of a forest of stars on k or more vertices. Furthermore,
ifT is a tree of order k, then sat(n, Â£>3;fc_3) < sat(n, T).
A perfect 3ary tree is a tree such that every vertex has degree 3 or degree 1 and all
vertices of degree 1 are the same distance from the center. For the remainder of this
thesis we will let Tk denote the perfect 3ary tree with diameter k 1 unless explicitly
stated otherwise. Kaszonyi and Tuza [28] observed that Tk1 is a P^saturated tree
for k > 3 and determined the saturation number for Pk when n is sufficiently large.
Theorem 2.26 (Kaszonyi and Tuza [28])
Let Pk be a path on k > 6 vertices and let Tk be the tree defined above. Let 3
3 2m~l 2 if k = 2m,
4.2m~l 2 ifk = 2m+l
Then, for n > a,k, sat(n, Pk) = n fff and every graph in SAT(n, Pk) consists
of a forest with
Tk1 C T.
n
ak
components. Furthermore, if T is a Pksaturated tree, then
If k < 5, then
1. sat(n,P3) = LfJ,
15
If if n = 0
2. sat(n, P4) = < (mod 2), and
ifn = 1
5. sat(n, P5) = n (_^J + l) .
In [22], the saturation numbers for some trees of small order, including brooms,
double stars, and subdivided stars, is determined. The saturation number for some
forests are also known. Building upon the work of Mader [33], Kaszonyi and Tuza
found the saturation number for matchings.
Theorem 2.27 (Kaszonyi and Tuza [28])
For n > 3m 3
sat(n, mK2) = 3m 3
and
SAT(n, mK2) = (m 1 )KS U (n 3m + 3)Ki
or m = 2, n = 4, and SAT(n, mK2) = id13.
One way to extend this work is to consider forests where every component is a
path; such a forest is referred to as a linear forest. Chen, Faudree, Faudree, Gould,
and Magnant [12] found bounds on the saturation number of an arbitrary linear forest.
Theorem 2.28 (Chen et al. [12])
For t > 2, let F = Pkl U Pk2 U U Pkt be a linear forest with k\ > k2 > > kt > 3
and let k = kt and q = kf) 1. Then, for n sufficiently large,
n n < sat(n, F) < ( ) + n q n q
_&k _ \2J
n
n
L2J
< sat(n, F) < ( ^ ) + n q
n q
Additionally, Chen et al. found the saturation numbers for
if k ^ 4
if k = 4
some linear forests of
small order. In joint work with Jill Faudree and Michael Jacobson, we characterize
16
the structure of iP^saturated graph with F(G) = P(G) and extend a result of
Chen et al. on sat(n, 3P3) to include all n > 9.
Theorem 2.29
For t > 1 and k > 2, if a connected graph G is tPksaturated of order n and size n,
then t = 2, the unique cycle, C, is a triangle and G E(C) is a forest of 3Pksaturated
trees.
Proof:
G is unicyclic by assumption. For cycle C in G, G E(C) is a forest. If G
contains a vertex of degree 2, then the neighbors of that vertex must be adjacent,
otherwise adding the edge between the two neighbors will not create a copy of Pk
that couldnt be replaced with an existing copy. Thus, if C\ > 4, then G C is a
forest consisting of V(G) trees. We will consider each tree in the forest to be rooted
at the cycle.
Assume that G E(C) contains a copy of Pk Among all the copies of Pk in G
E(C), choose a copy such that the distance between V(C) and V(Pk) is maximized.
Let v G V(Pk) be a vertex such that d(v,C) = d(Pk,C). If k yt 3, then there is
another vertex, u, of the Pk that is nonadjacent to v. Since G is tPksaturated,
adding uv should create tPk where one of the paths must use edge uv. By our choice
of v there is no part of a copy of Pk among the decendents of v including v, except
the copy of Pk that uses edge uv. This implies that there are t 1 copies of Pk in G
that do not use v or any of vs decedents. This is implies there is a copy of tP3 in G,
a contradiction. We now consider the case when k = 3.
When k = 3, v is the middle vertex of the P3 as there are no vertices of degree
2. But this gives a vertex adjacent to two vertices of degree 1, a contradiction. Thus,
every copy of Pk in G must use at least two vertices of C.
17
Using the previous sentence, we observe that if V(C') > 3, adding the edge
between two vertices a distance 2 away on C implies U(C') > 2t + 1.
We know G contains t 1 copies of Pk Choose some collection of t 1 copies of
Pk in G such that they use as few vertices of C as possible.
If t > 2, there exist at least two copies of Pk in C. Label the vertices of C in
order starting with the first of the PGs in G : ay, ay, With out loss of generality,
assume the first Pk uses ay through ay. Since G has another Pk, we know C contains
an xi+\ that is not adjacent to ay.
Add edge ayay+i. Now the only Pk in the copy of tPk that uses vertices in
{ay,...,ay+i} uses the edge ayay+i, otherwise we could have chosen a copy of (tl)Pk
that used fewer cycle vertices. So we can replace the copy of Pk that uses edge ayay+i
with the first Pk, which uses only cycle vertices in {ay,... ay}, but this gives a copy
of tPk in G, a contradiction.
Thus, t = 2. We now show that C = C3. Assume not. So C must have at least
2t+ 1 vertices and since t = 2, C has at least 5 vertices. G must contain a copy of Pk
Choose the copy, that uses the fewest number of cycle vertices. Label the vertices
of the cycle clockwise, from ay to ayt+i, and choose the labeling so that the vertices of
on the cycle are labeled ay,..., ay. We note that j ^ 1, otherwise, by our choice
of G is not 2Pk saturated. Further j yt 2t + 1, since adding any chord to the cycle
would not create a copy of 2Pk. Also j ^ 2, as G E(C) does not contain a copy of
Pk Thus ayay ^ E(G).
Add edge ayay Now there must be two copies of Pk, but only one copy can use
vertices in {ay ... ay} by our choice of Thus there is a copy of Pk that uses only
cycle vertices in {ay+i,... ,ay*+i}, but this path together with gives 2Pk in G, a
contradiction. Thus C = C3.
Now we will show that G C must be a forest with 3 components. Assume to
the contrary that there is a vertex of the cycle with degree 2. Let x,y, and z be the
18
vertices of the cycle. First, G C is not empty because C3 is not 2Pfcsaturated for
any k. So G C must contain at least one nontrivial component. Let v be a vertex
at distance one from x, T be the tree containing v, and y a vertex of degree 2. The
edge vy must create a copy of 2Pk The copy of Pk that contains vy does not contain
z or x since every copy of Pk in G must use two cycle vertices. So the copy of Pk
that contains vy uses only one edge outside of T. But replacing this edge with vx
would then create a copy of Pk in T, a contradiction. So G E(C) is a forest with 3
components.
Next we will show that d(x) = d(y) = d(z) = 3. Let Tx,Ty,Tz be the trees in
G C rooted at x,y,z respectively. First suppose that d(x) = 3 and d(y) > 3. Let
v be the neighbor of x in Tx. The edge vz must create a copy of Pk and there must
be another copy in Ty U x. Since d(y) > 4, there is no vertex at distance k 2 from
y in Ty, otherwise Ty would contain a copy of Pk This implies that there is no copy
of Pk in Ty U x. So either d(x) = d{y) = d{z) = 3 or d(x) > 4, d(y) > 4, d{z) > 4.
Assume that d(x) > 4, d(y) > 4, d(z) >4. So r has degree at least 2 in Tx (the
same is true for y and z). Set Pxv to be a path that starts at x, contains edge xv
and has maximum length with that choice of v. Let l = min{h : d = \PiV\, i G
{x,y,z}, v G NT.(i)}. Without loss of generality, say that \PXV\ = l. Observe that
since the longest path in Tz has fewer than k vertices and each path starting at z has
at least l vertices, the maximum length path in Tz with an endpoint at z has length
at most k l 2. Consider adding the edge vz. So that maximum path together with
vz and a path containing only decedents of v contains less than k vertices. So a copy
of Pk that contains edge vz must use vertex x. This implies that Ty must contain a
copy of Pk, a contradiction. Therefore d(x) = d(y) = d(z) = 3.
Finally, suppose that Tx is not P^saturated. Since there is no copy of Pk in Tx
there exists an edge uv in Tx such that Tx + uv does not contain Pk. Thus the only
copies of Pk in G that contain uv must contain at least 2 cycle vertices. This implies
19
that there is one of Ty or Tz that contains a copy of Pk, a contradiction. Thus each
tree in G C must be Pk saturated.
Lemma 2.30
sat(n, 3P3) < _22y^J for n > 11
Proof: Let k = So we have 2N3 U kP2 C SAT(n, 3P3) for n even, and
Proof: The value of sat(9, 3P3) was obtained via computer search; the code for
the computer search is given in Figure 2.2. There is a unique graph in SAT(9. 3P3),
which is given in Figure 2.1a.
We begin by showing sat(10, 3P3) = 11. First note that the graph given in Figure
2.1b is a 3P3saturated graph of order 10 and size 11. Now suppose G is a graph of
2N3 U kP2 U Pi C SAT(n, 3P3) for n odd.
Lemma 2.31 (Chen et al. [12])
If t > 2 and k > 3 are integers, then no tPksaturated graph is a tree.
Theorem 2.32
if n = 9
(a) The unique graph in (b) The unique graph in
SAT(9,3 P3)
SAT(10,3 P3)
Figure 2.1: 3P3saturated graphs.
20
def is_sat(G,H):
if G.subgraph_search(H, induced=False) is None:
for i in (G.complement().edges(labels=False)):
G.add_edge(i)
if G.subgraph_search(H, indueed=False) is None:
return False
G.delete_edge(i)
return True
else:
return False
ThreePThree = Graph([(0, 1, None), (1, 2, None),(3, 4, None), (4, 5, None),
(6, 7, None), (7, 8, None)])
for g in graphs(9):
if is_sat(g, ThreePThree):
g. showQ
Figure 2.2: Sage Code Used to Find SAT(9,3Ps)
21
order 10 that is 3P3saturated. Lemma 2.31 implies that the only components of a
3P3saturated graph that can be trees are isolated vertices or isolated edges. If G has
an isolated vertex, v, then G v must be 3P3saturated, and hence If(G) > 14. If
G has an isolated edge, uv, then G[V(G) uv] must be a complete graph. Otherwise
adding an edge to G[V(G) uv] would not yield a copy of 3P3. Thus If(G) = 29.
Therefore no component of G is a tree.
It was shown in the proof of Theorem 2.29 that if a component of a tP3saturated
graph has size equal to its order, then that component is the net. So if G has a
component with size equal to the order, then G contains a copy of the net. This
leaves 4 remaining vertices in G that must form a complete graph. Since the net is
2P3saturated, adding any edge among these 4 vertices will not create a 3P3. This
implies \E(G)\ = 12. Therefore every component of G has size larger than its order
and hence \E(G)\ > 11.
We now have sat(9, 3P3) = 14 and sat(10, 3Ps) = 11. Notice that sat(ll, 3P3) <
11 since the graph in Figure 2.1b together with an isolated vertex is 3P3saturated
on 11 vertices. Let G be a graph in SATfll, 3Pz). Notice G is not connected since
the only 3P3saturated graph with order equal to size is the net. G must contain
a component of order at most 5. Let C be the smallest component of G. Since
all components of order less than 6 in a 3P3saturated graph are complete, C is
complete. If the order of C is 4 or 5 then there are not enough edges to connect
the remaining vertices of G which contradicts our choice of C. Since no component
of a 3P3saturated graph is a Jd3, we conclude that C is P2 or P1. If C is P2, then
G C must be 3P3saturated and hence have at least 14 edges. So we conclude that
G contains an isolated vertex, which implies sat(11, 3P3) = 11.
Lemma 2.30 implies that sat(12, 3P3) < 12. Let G be a graph in SAT(12, 3P3). If
G has a component that is a tree it must be P2 or P\. If G contains P2 as a component,
then \E(G) \ > 12, since G P2 must 3P3saturated. If G contains P\ as a component,
22
then G P\ must be 3P3saturated, since the only 3P3saturated graph of minimum
size on 11 vertices contains an isolated vertex, we have P(G) > 12. If G contains
no component that is a tree, we also have P(G) > 12, thus sat(12,3P3) = 12.
Claim 2.33
For k > 0 and n = 2k + 11, every graph in SAT(n, 3P3) contains a component
isornorphic to Kx.
Assuming the claim is true, we will show sat(n, 3P3) > for n > 12;
together with lemma 2.30 this will give the desired result. Let k > 12 and G be
a graph in SAT(fc,3P3). Since Lemma 2.30 implies that sat(fc, 3P3) < fc, there
must be some component of G that is a tree, which is either P2 or Pi. If P2 is a
component of G, then G P2 must still be 3P3saturated; thus by the induction
hypothesis, G P2 contains
(fc2)+12
2
edges, hence G contains edges If
Pi is a component of G, then G Pi must still be 3P3saturated. If k is odd, then
= , and thus we have the desired result. In the case that k is
(fc1) + 12
2
even, we have
(fc1)+12
2
: 1_^^J 1 By Claim 2.33, we know every graph in
SATO 1 3P3) contains an isolated vertex. Since there cannot be two isolated
vertices in any 3P3saturated graph, we know that G Pi is not 3P3saturated of
(fc1)+12
2
+ 1 edges. Therefore we have
minimum size and therefore contains at least
sat(n, 3P3) = [^\
It remains to prove Claim 2.33. Suppose that G is a graph in SAT(n, 3P3) for
n = 2k + 11. Notice that the claim holds for fc = 0 as shown above. From Lemma
2.30, we know that G has at most fc + 11 edges so G contains at least fc components
that are trees. Lemma 2.31 implies that each of these trees must be P2 or Pi. If
G contains an isolated vertex then we are done, so all the trees in G must be P2.
G kP2 must be 3P3saturated, but G kP2\ = 11. Hence G kP2 must have at
least 12 edges since the only 3P3saturated graphs of minimum size on 11 vertices
23
contain an isolated vertex. Since if(G) < k + 11, we conclude that G contains an
isolated vertex.
2.3 Saturation Spectrum
In this section we will give a summary of results pertaining to the saturation
spectrum for graphs. The first result is due to Barefoot, Casey, Fisher, Fraughnaugh,
and Harary [7].
Theorem 2.34 (Barefoot et al. [7])
For n > 5, there exists a K3.saturated graph of order n with m edges if and only if it
is complete bipartite or
2n 5 < m <
(n l)2
4
+ 1.
The previous result was extended by finding the saturation spectrum for all com
plete graphs.
Theorem 2.35 (Amin, Faudree, Gould, and Sidorowicz [5])
Let p,n,q,r be integers such that p > 4, n > 3(p + 4), n = (p 1 )q + r, and
0 < r < p 2. There is a Kpsaturated graph with n vertices and m edges if and only
if either
Op 1)
2 < m <
[jp 2 )n2
2 n + r(r + 2)
2 (p ~ 1)
r(p ~ 1) 1
(2.4)
or m = if(G) for some complete (p l)partite graph G on n vertices.
Moreover, Amin et al. show that for each m in 2.4 there is a non (p l)partite
idpsaturated graph of size m.
The saturation spectrum for small paths is also known. Gould, Tang, Wei, and
Zhang [27] observe that sat(n,P3) = ex(n, P3), hence spec(n,P3) is continuous.
They also observe that it is straightforward to transform a graph in SAT(n, P4) into
24
a graph in SAT(n, P4), where at each step the size of the graph increases by exactly 1.
Hence, spec(n, P4) is continuous. They also determine spec(n, P5) and spec{n,Pf).
Theorem 2.36 (Gould et al. [27])
Let n > 5 and sat(n, P5) < m < ex(n, P5) be integers, m E spec(n, P5) if and only
if n = 1,2 (mod 4); or
m E <
{f 3,f 2,f 1} %fn = 0 (mod 4)
{^} ifn = 3 (mod 4).
Theorem 2.37 (Gould et al. [27])
Let n > 10 and sat(n, P&)
if (n, m) i {(10,10), (11,11), (12,12), (13,13), (14,14), (11,14)} and
{2n 4, 2n 3, 2n 1} if n = 0 (mod 5)
m
i {2n 4}
{2n 4}
if n = 2 (mod 5)
if n = 4 (mod 5).
25
CHAPTER 3
SATURATION SPECTRUM OF STARS AND PATHS
This chapter contains joint work with Jill Faudree, Ralph Faudree, Ron Gould,
and Michael Jacobson.
3.1 Stars
In this section we will show that the saturation spectrum of idl t contains all
values from the saturation number to the extremal number. The following theorem
is the main result of this section.
Theorem 3.1
Let S = K\ t for t > 3. If n > t + 1, and sat(n,S) < m < ex(n,S'); then m E
spec(n, S).
Before proving Theorem 3.1, we give two lemmas that describe edge exchanges that
can be used to transform a Al tsaturated graph G into a Al tsaturated graph with
one more edge. We will refer to the exchange in Lemma 3.2 as a Type I exchange
and the exchange in Lemma 3.3 as a Type II exchange.
Lemma 3.2
In a Kitsaturated graph G, if there is vertex v of degree at most t 3 that is nonadja
cent ton orw where uw E E(G) and d(u) = d{w) = t 1, then G' = Guw+{vw, vu}
is Ki>tsaturated vnth e(G') = e(G) + 1.
Proof: First note that the degrees of dciu) = dc'(u), dciw) = dc'(w), and dciv) +
2 = dc'iv). Since dciv) < t 3, it is easy to see that no vertex of degree t is created
and hence idl t is not a subgraph of G'. Now consider e G E(G'). If e is incident to u
or w, then G' + e contains idl t since u and w are both of degree t 1. If e is incident
to v, then G' + e contains idyt, otherwise G would not be idl tsaturated. Similarly,
if e is is not incident to u, v, or w, then G' + e contains idyt, otherwise G would not
be idi;tsaturated.
26
t 1
t 1
Figure 3.1: Type I exchange
t1
i 1
T
> i i i
i 4
t 1
< i 1
i 1
Figure 3.2: Type II exchange
Lemma 3.3
In a Ki tsaturated graph G, if there are vertices V\ and v2 of degree at most t 2
and an edge uw such that u and w are of degree t 1 where viw,v2u E{G), then
G' = G uw + {viw,v2u} is Ki>t,saturated with e(G') = e(G) + 1.
Proof: First note that the degrees of dciu) = do'(u), dciw) = do'iw), do(vi) + 1 =
do'(vi), and dc(v2) + 1 = dG'(v2). Since do(vi) < t 2 and dc(v2) < t 2, no vertex
of degree t is created centered at V\, v2, u or w. Hence Ki>t is not a subgraph of G'.
Now consider e G E(G'). If e is incident to u or w then G' + e contains Ki>t since u
and w are both of degree t 1. If e is incident to v\ or v2, then G' + e contains K\yt
otherwise G would not be fdi)tsaturated. Similarly, if e is is not incident to V\, v2, u,
or w then G' + e contains Ki>t, otherwise G would not be if ^saturated.
The proof for Theorem 3.1 is split into cases according to the number of vertices
in the host graph G relative to t. To ease reading, cases are listed as lemmas.
Lemma 3.4
Let n = t + 1. For each t > 3 and m such that sat(n, ifgt)
exists a Kiytsaturated graph G with e(G) = m.
27
Proof: We construct a sequence of Ai)tsaturated graphs, G\,... Gs where e(Gi) +
1 = e(Gi+1), and this sequence contains a graph of each size from sat(n, fdpt) to
ex(n, Ki>t). Let G\ = Kt U {u}. By Theorem 2.24 we see that G\ G SATfa, Km).
In order to construct the sequence of graphs we will need a large matching from Kt,
so that we may use type I exchanges. Let M be a maximum matching of Kt; clearly
M contains \t/2\ edges. Now, to create Gi+\ from Gi, we use an edge of M and v to
perform a type I exchange. Lemma 3.2 implies that Gi+1 is a fdltsaturated graph
with e(Gi+1) = e(Gi) + 1. We note that we can preform \t/2\ type I exchanges when
t is odd so that Gs = Gp/2j is a (t l)regular graph. When t is even we can preform
t/2 1 type I exchanges so that dca(v) = t 2 and all other vertices in Gs are degree
t 1. Notice that in either case, Gs is the extremal graph.
Lemma 3.5
For each t > 3, t + 2 < n < y and m such that sat(n, fdpt)
exists a K\ttsaturated graph of size m.
Proof: To show this, we will construct a sequence of fdi)tsaturated graphs,
G\,...GS, that contains a graph of each size from sat(n, Kiyt) to ex(n, Ki>t). Let
G\ = Kt U Kn_t By Theorem 2.24, we see that G\ G SATfn. K^t). In order to
construct the sequence of graphs, we use large disjoint matchings from Kt so that we
may use type I and type II exchanges. It is well known (cf. [11]) that Kt contains
t 1 matchings, M1;..., Mt_i, each of size _J. Since n < 3t/2 implies n t < t/2,
each one of the the t 1 matchings can be associated with a vertex of Kn_t. For
convenience, let V(Kn_t) = {ui,... ,ura_t} and say that Vi is associated with Mj for
1 < i < n t.
Starting with Gi, iteratively change the degree of each vertex in fdra_t from nt 1
to t 1. In order to do this, each vertex in V(Knt) needs 2t n more incident edges.
Proceed based on the parity of 21 n. If 2t n is odd, pair the vertices in fdra_t
28
so that Vi is paired with Vi+\ for each odd i < n t. Note that when n t is
odd, vnt is unpaired. Associate each of the pairs with an edge from Mra_t+i. Then,
iteratively use each pair and associated edge to preform a type II exchange to create
dr2, G ^n t  ^j .
Notice that in G^n=t+1 j it is possible that ry is adjacent to some vertex in Mj.
Thus there are at least [t/2\ 1 edges in Mj that are not incident to ?y. Create the
remaining graphs in the sequence by preforming (2t n l)/2 type I exchanges with
each Vi and Mj. In order to preform (21 n l)/2 type I exchanges, it must be
verified that (21 n l)/2 < \t/2\ 1, otherwise Mj has too few edges to preform
the type I exchanges with iy. Since n > t + 2, it follows that:
n > t + 2
t 3 >
1 >
1 >
2t n 1
2t n 1
2
2t n 1
2
Lemma 3.2 and 3.3 imply that after completing the (21 n l)/2 type I exchanges
and a type II with each Uj, we have d(vi) = t 1 for 1 < i < n t 1. Further, if
n t is odd, then d(vnt) = t 2 and if n t is even then d(vnt) = t 1. In either
case, it follows that Gs is the extremal graph.
Now consider the case when 2t n is even. In this case, only type I exchanges will
be used. Construct G2,..., Gs by preforming (21 n)/2 type I exchanges using each
Vi and associated Mi. It remains to verify that (21 n)/2 < \t/2\ so that (21 n)/2
29
type I exchanges can be completed. Again, since n > t + 2, it follows that:
n >
t 2 >
t 2
2
t
2
>
>
t + 2
2t n
2t n
2
2t n
2
Finally, Lemma 3.2 implies that after completing the (2t n l)/2 type I exchanges
to each Vi that d(vi) = t 1. So, it follows that Gs is the extremal graph.
Lemma 3.6
For each t > 3, n > // and m such that sat(n, ffi;t)
Kitsaturated graph of size m.
Proof: Proceed in a fashion similar to the proof of Lemma 3.5. Construct a
sequence of if ^saturated graphs, G\,... Gs, that contains a graph of each size from
sat(n, Ki>t) to ex(n, ifi;t). Begin by constructing a (t l)regular (or nearly regular
depending on the parity of n and t) graph, G', on r vertices where r = n suc^
that G' has a sufficient number of large matchings for the algorithm. A well known
result (cf. [11]) shows that a complete graph Kr decomposes into r 1 matchings of
size r/2 when r is even or hamilton cycles when r is odd will be used.
First suppose that r is even. To form G', begin with a matching decomposition
of Kr = Mi U U Mr_i. Let G1 = Mi U U Mti. Clearly G1 is (t l)regular and
contains t 1 disjoint matchings, Mi,... Mti, of size r/2.
When r is odd, begin with a hamiltonian cycle decomposition of Kr = Ci U U
C(ri)/2 If t 1 is even, then let G' = Ci U U C'(t_i)/2 If t 1 is odd, then let
G1 = Ci U U C(t~2)/2 U M where M is a maximum matching of Ct/2 In this case
there is a single vertex of degree t 2; all other vertices are of degree t 1. Further,
since each hamiltonian cycle of Kr contains two disjoint matchings of size (r l)/2,
30
G' contains t 1 disjoint matchings, Mi,..., Mt1, of size at least (r l)/2.
Let Gi = G' U Kytij and label the vertices in V(G') = {u\,... and
V(Kl j ) = K ,... If r and t 1 are both odd, then a single edge from the
vertex of degree t 2 in G' is added to a vertex in A/tij. Without loss of generality
let this edge be uiVyty Theorem 2.24 implies that Gi is a minimally A/tsaturated
graph. Associate each vertex ry with a matching Mi in G'.
Starting with Gi, iteratively change the degree of each vertex in Kytij from
_^/J 1 to t 1. Each vertex, Vi, needs _f J more incident edges. Notice that when
r and t 1 are both odd that only _fJ 1 incident edges need to be added to u^t+ij.
Proceed based on the parity of _fj If LfJ is dd, then pair the vertices in Kytij
so that Vi is paired with Vi+\ for each odd i < _^rJ Note that if L^rJ is odd then
Vytij is unpaired. Associate each of the pairs with an edge from Mytij+1 Then,
iteratively use each pair and associated edge to preform a type II exchange to create
G2,... GLtJ+1.
2
Notice that in G[tj+1 it is possible that ry is adjacent to some vertex in Mi.
2
Thus there are at least _r/2J 1 edges in Mi that are not incident to ry. Create the
remaining graphs in the sequence by preforming (l/2)(_t/2j 1) type I exchanges
with each ry and Mj. In order to preform (1/2)(_t/2j 1) type I exchanges, it must
be verified that (l/2)(_i/2j 1) < _r/2J 1. Since n > y, it follows that:
r = n +
>
31
~2
t + 1
2
t + 1
2
> t 1.
As r and t are both integers, it follows that r >t, hence (1/2)(_t/2j 1) < _r/2J 1.
Lemma 3.2 and 3.3 imply that after completing the (l/2)(_t/2j 1) type I exchanges
and a type II with each ry that d(vi) = t 1 for 1 < z < _^rJ 1 Further, if _^rj
and t 1 are odd and r is even, then d(vytij) = t 2. Otherwise d(vyt+i^) = t 1.
31
In either case it follows that Gs is the extremal graph.
Now, consider the case when _fj is even. In this case only type I exchanges
will be used. Create G2, ,GS by preforming (l/2)(_i/2j) type I exchanges using
each Vi and associated Mi. Since r >t, it follows that (l/2)(_i/2j) < _r/2J so that
(l/2)(_i/2j) type I exchanges may be done with each vertex ?y.
Finally, Lemma 3.2 implies that after completing the (l/2)(_t/2_) type I ex
changes to each ry that d(vi) = t 1 for 1 < z < L^J 1 If r and t 1 are odd,
then h(u^tij) = t 2 otherwise d(v^tij) = t 1. Again, in either case it follows that
Gs is the extremal graph.
Theorem 3.1 follows directly from Lemmas 3.4, 3.5 and 3.6.
3.2 Paths
In this section we show that when n is sufficiently large, spec(n, Pk) contains all
values from sat(n, Pk) to ex(n, Pk) c, where c is a constant that depends on k. The
following is the main result of the section.
Theorem 3.7
Let P = Pk If n = r(k 1) + ak *) (k 1)] + ft, where 0 < ft < k 1 and
sat(n, P) < m < + ak [t^1) (k 1)] + ft 1, then m E spec(n, P).
As in the previous section we provide two lemmas that transform a P^saturated
graph G into a P^saturated graph with one more edge. Let ak = Tfci An immedi
ate consequence of the proof of Theorem 2.26 in [28] is that there exists P^saturated
trees of every order p such that p > ak Let v be a vertex with pendant neighbors
in Tk1. The graph obtained by adding additional pendant vertices to v in Tk\ so
that the order of the new graph is p will be denoted Tf_t (See Figure 3.3). Clearly,
Tvk_x E SAT( n, Pk). Let T^_1 denote a P^saturated tree of arbitrary order.
Lemma 3.8
Let G be a Pksaturated graph that contains two components, Tffl and Tff1. If H =
G{Tki>Tki\> then G' = HUTff^P2 is a Pksaturated graph where e(G') = e(G) + l.
32
Figure 3.3: P515
Proof: Let p = pi + P2 Since Tf_t and G are P^saturated, it follows that G'
does not contain Pk. Let e G E(G'). In order to show that G' + e contians Pk, we
will consider several cases. First, if e G ff(T^_1), then T'_1 +e contains Pk since T'_1
is Pfcsaturated, hence G' + e contains Pk Now since G is P^saturated, if e G E(H),
then G' + e contains Pk Now suppose that e has at least one endpoint in V(H) and
one in V(T^_1). Notice that El U T^_i is an induced subgraph of G'. If G' + e does
not contain Pk, then by deleting pendant vertices not incident to e it can be seen that
H U + e does not contain Pk, since deleting vertices can not create a copy of Pk
This implies that G is not P^saturated, a contradiction. Therefore G' is P^saturated.
Finally, note that e(G) = e(H) + {p\ 1) + {jp2 1) and e{G') = e(H) + {p\ +P2 1),
thus e(G') = e(G) + 1.
Lemma 3.9
Let k > 5 and G be a Pksaturated graph. Let p be an integer such that p > (k 1) +
cik [(k^1) (k 1)]. Let T^'_1 be a component of G and F = [^f1) {k 1)] Tf_l
such that \F\= p k + l. If H = G T^'_1 then G' = H U Kk1 U F is a Pksaturated
graph where e{G') = e(G) + 1.
Proof: Notice P is a forest of P^saturated trees. By Theorem 2.26 each
component of P must have order at least a*,. Since p > {k \)+ak [t^1) (k 1)], it
follows that P > ak [{kf:) {k 1)]. Hence, P is large enough for each component
to be a Pfcsaturated tree.
33
Note that e(G) = e(H) + p 1 and e(G') = e(H) + (fc21) + e(P). Since P
is a forest on p k + 1 vertices and [(fc21) (k 1)] components, it follows that
e(P) =pk + 1 [(k~1) (fc  1)]. Thus e(G') = e(H) +p = e(G) + 1.
It now remains to show that G' is P^saturated. Let e G E(G'). First, suppose
that e G F(P). It follows that G' + e contains Pk since F is P^saturated by Theorem
2.26. Now suppose that has both endpoints in V(H). Clearly, since G is P^saturated,
G + e contains a copy of Pk such that V(Pk) G V(H). Thus G' + e contains a copy of
Pk. Finally, suppose that e has one endpoint in H and one in P. Assume that G' + e
does not contain Pk. Let T be the component of P incident to e. Let G = G'\H U T],
Notice G + e does not contain Pk. Further since G = H U T^'_1 and G = PI U T differ
only in the number of pendants adjacent to the vertex of highest degree in T and
h is easy to see that G + e does not contain Pk. Thus G' is P^saturated.
The transformation in Lemma 3.8 will be referred to as a tree exchange and the
transformation in Lemma 3.9 will be referred to a clique exchange. We are now ready
to prove Theorem 3.7.
Proof: Beginning with a minimally P^saturated graph, we will build a sequence
of Pfcsaturated graphs, G\,..., G/, of size sat(n, P) to + [t^1) (k 1)] +
(31 where e(Gi+1) = e(Gj) + l for 1 < i < f 1. Let G\ = qTkUT(; where q = _^yj 1.
Theorem 2.26 implies that Gi G SAT(n, Pk). Once G is built, use one of the following
exchanges to build Gi+
1. If Gi contains two components and T(((_1, then use a tree exchange to create
Gj+i
2. If Gi contains exactly one tree component and the tree has at least
fk 1
V 2
(kl)
+ (kl)
vertices, then use a clique exchange to obtain Gi+\.
34
Lemmas 3.8 and 3.9 imply that when either a tree exchange or a clique exchange
is used, Gi+\ is a P^saturated graph with e(dd+1) = e(dd) + 1. As long as there are
at least two tree components or there is a single tree component T in Gi such that
IU > at [(V) (* 1)] + (* 1). one of the exchanges can be used to build db+i.
So the final graph built by the algorithm will have one tree component of order less
than ak [f^1) (k 1)] + (k 1).
Since n = r(k 1) + ak [(k1) (k 1)] + /?, it follows that upon constructing
Gi = (r l)idfc_iUT^_1 that Tk_f = ak (k 1)] +(k l)+/3. Thus another
clique exchange can be used followed by tree exchanges to produce rKk_1 U T^_v At
this point, it is easy to calculate q = ak [(fc21) (k 1)] +/3 < ak [(fc21) (k 1)] +
(k 1). So the algorithm will terminate with Gf = rKk~i U Tk_v Thus:
e(Gf)
k 1
2
r + [n
k 1
2
r + ak
r(k 1) 1]
k 1
2
(k 1)
+
1.
Note that the algorithm in Theorem 3.7 could be altered to include exchanges
with Pfcsaturated graphs other than T^'_1 and Kk_ 1. However, the following theorem
will show when n is large, the algorithm gives P^saturated graphs to within a constant
of the extremal number.
Theorem 3.10
For n sufficiently large and k > 5, spec(n, Pk) contains all values from, sat(n, Pk) to
ex(n, Pk) c where c = c{k).
Proof: Let n be expressed as n = r{k 1) + ak _ if 1)] + /?, where
f3 is a constant such that 0 < [3 < k 1. The algorithm in the proof of Theorem
3.7 gives a sequence of P^saturated graphs that contains graphs of each size from
sat(n, Pfc) to (kg1)7, + ak [(fc21) (k 1)] + [3 1. Let G be a P^saturated graph of
35
size (fc21)r + afc [(k21) (k l)]+/31. Theorem 2.9 implies that ex(n, Pk) < ^ .
Now it is possible to estimate ex(n, Pk) e(G) as follows:
ex(n, Pk) e(G) <
(k 2 )n
k 1
r + ak
k 1
(fc1)
+ /3 1
(fc 2){r{k l) + ak [(V) (k 1)] + /?)
fc 1
r + ak
k 1
(fc1)
+ (3 1
fcA  (fc2)[afc[(fc1)(fcl)]+/3]
2 / 2
fc 1
r + ak
k 1
(fc1)
+ /3 1
= (fc ^afcp1) afc(fc 1 )(fc 4) + (fc 4)/3
2
< ^ 2 ) ~ ~ ~ 1) ^
+ 1
Thus, for a fixed fc the difference between ex(n, Pk) and e(G) is a constant for all n
sufficiently large.
Recently Balister and Dogan [6], have shown for k large and e > 0 that c{k) <
(y/2 + e)fc3/2. Furthermore, up to the constant y/2, this is the best upperbound. In
Chapter 5, it is shown that spec(n, Pk) does not contain values from ex(n, Pk)
+ 1 to ex(n, Pk) 1.
36
CHAPTER 4
SATURATION SPECTRUM OF BROOMS
This chapter contains joint work with Jill Faudree, Ron Gould, and Michael
Jacobson.
4.1 Saturation for BSyt
Unlike stars and paths, the saturation number for brooms is not known in general.
We will begin this chapter with by providing an upperbound on the saturation number
for brooms.
Let Tk_i be the perfect 3ary tree with diameter k 1. It is useful to view Tk_i as
a rooted tree, where the root r is the center of Tk_i. When fc 1 is odd r is a vertex,
otherwise r is an edge. We will say that a vertex v is at level i if d(v, r) = i. Notice
that all degree 1 vertices in Tki are at level We will refer to each component
of Tfc_i r together with any adjacent root vertex as a branch. Let Tk_i;t be the
graph obtained by attaching pendants to 2 vertices from different branches (if k 1
is even the branches must contain different vertices of the root) at the penultimate
level of Tfc_i so that Tk_ i;t has two vertices of degree t + 1.
Lemma 4.1
Given t > 2 and s > 4, TSyt is BSyt saturated.
Proof: Since TSyt is Ps+isaturated it follows that TSyt is BSytfree. Thus, it suffices
to show that adding any edge to TSyt crates a copy of Ps+1 where the penultimate vertex
has degree at least t + 1. Let u and v be the vertices of degree t + 1 in TSyt. Consider
TSyt + xy. Suppose that x is on level i and y is on level j where i < j.
Claim 4.2
Let B be a branch containing a vertex of degree t + 1 in TSyt. If there is a path P in
Ts>t + xy such that
37
P has order at least _yyj + 2,
ends at a root vertex,
and V(P) Pi V(B) = 0 unless s is odd in which case \ V(P) fl V(B) \ = 1,
then Ts>t + xy contains Bs>t.
Proof of Claim 4.2 Notice the vertices of P are disjoint from V(B) unless s
is odd, in which case the intersection contains only the root. There is a path Pu
from the root to u of order If s is odd, then  V(P) fl V(PU) \ = 1, otherwise
\V(P) nV(Pu)\ = 0. Hence, PUPU is a path in Ts>t + xy with at least [yyj + [yyj +
2 \P fl Pu\ = s vertices that ends at u. It follows that PUU P U N(u) is a copy of
Bs t. This completes the proof of Claim 4.2.
We will break the remaining portion of the proof into cases based on the location
of x and y in Ts>t.
Case 1: y is a descendent of x or x is in the root. Since x and y are
nonadjacent in TSyt there is a path, Px, on a least 3 vertices connecting x and y. Let
x' be the vertex of Px on level i + 1 (If s is even and x is in the root, then x' is on
level i when x is not in the branch containing y). Notice that x' has a descendant, z,
that is is not on Px. Let Pxj be a path starting at x' to a vertex of degree 1 through
z. Notice that TSyt[Px U Px>] + xy contains a spanning path ending at x. This path
together with the path from x to the root create a path, P, of order at least _yyj +2.
Since all the vertices of P are contained in a single branch Claim 4.2 implies that
Ts>t + xy contains Bs>t.
Case 2: x and y are in the same branch. Since we are not in case 1, we
may assume that y is not a descendant of x. Let Px be a path from x to a vertex
of degree 1 containing only descendants of x. Since x is on level i, Px contains at
least i + 1 vertices. Let Py be the path from y to the root. Notice that
Px U xy U Py = P is a path on i + l+j + 1 vertices. Since i < j, P has order
38
at least [Ay1] + 2. Again the vertices of P are contained in a single branch. Thus,
Claim 4.2 implies that TSyt + xy contains BSyt.
Case 3: x and y are in the different branches. First suppose that x, y,
and u are contained in different branches and s is odd. Let Px be a path from x to a
vertex of degree 1 containing only descendants of x. Since x is on level i, Px contains
at least [Ay^] i + 1 vertices. Let Py be the path from y to the root. Notice that
Px U xy U Py = P is a path on [A^] i + l+j + 1 vertices. Since i < j, P has
order at least [Ay,] + 2. The vertices of P only intersect the vertices of the branch
containing u at the root. Thus Claim 4.2 implies that TSyt + xy contains BSyt.
Now suppose that x, y, and u are contained in different branches and s is even.
If the branches that contain x and y do not contain the same root vertex as the brach
containing u, then the proof is the same as when s is odd. Suppose that one of x or
y has the same root vertex as the branch containing u. There is a fourth branch B
that does not contain any of x, y, or u. A maximal length path, Pb, in B starting at
the root contains [Ay1] + 1 vertices. Let Px and Py be paths from the root to x and y
respectively. Since x is on level i and y is on level j, it follows that Pb U Px U Py U xy
is a path, P, on at least [A^] + 2 + i + j vertices. Let Pu be the path starting at the
root and ending at u. Notice that P U Pu is a path on 2 [A^] + 1 + i + j vertices.
Since neither x or y are in the root we have i > j > 1. Thus, 2 [Ay,] + 1 + i + j > s.
Thus TSyt + xy contains Bs t.
Finally suppose that x is in the branch containing u and y is in the branch
containing v. In this case, there is a third branch, which shares a root vertex with the
branch containing x, that has a path P' starting at the root on [Ay1] +1 vertices. Let
Py be a path from the root to y, and Px be a path from x to u. Now P = P'UPyUxyUPx
is a path on at least on at least s vertices that ends at u. Thus, TSyt + xy contains
Bs,t
39
Observe that using Lemma 4.1 it is possible to show a forest of trees T*t is BSyt
saturated. Faudree, Faudree, Gould, and Jacobson proved that in some specific cases
TSyt is a P^saturated tree of minimum size and determined the saturation numbers
for those brooms.
Lemma 4.3 (Faudree et al. [22])
For t > 2 and n sufficiently large, sat (n, Biyt) = n ([fjqfj + l) and sat (n, B5yt) =
Lemma 4.4 (Faudree et al. [22])
For n > Ts+i and s> 5, sat(n, BSy2) = sat(n, Ps+i).
These results along with Lemma 4.1 motivate the following conjecture.
Conjecture 4.5
Let s > 4 and t > 2. If n is sufficiently large and T is a BSytsaturated tree then
\T\ > \TSyt. Moreover, ifbSyt = \TSyt\, then sat(n,Bs>t) = n f .
4.2 Saturation Spectrum for Bs t
From the results of the previous section it can be observed that there is a family
Â£>s)tsaturated graphs with similar structure to the sequence of P^saturated graphs
used in the proof of Theorem 3.7. Motivated by this observation, we will prove an
analogue of Theorem 3.7 which pertains to brooms.
The tree obtained by adding vertices to Ts>t (by adding additional pendants to
one of the vertices of degree t +1) so that the resulting tree has order p will be denoted
T%t. Since Ts>t is Ps+ifree and duplicating pendants does not lengthen the longest
path it follows that Tft is Ps+ifree. This fact and Lemma 4.1 imply that Tft is BSyt
saturated. Let Tft denote a PS;isaturated tree of arbitrary order and bSyt = \TSyt\.
The following is the main result of this section.
40
Theorem 4.6
Let s > 3 and t > 2. If n
0
f/ien to G spec(n, 5S;t).
r(s + t 1) + bSyt [(s+2 *) (s +t 1)] +f3 where
+ 6S)t [(s+*1) (s + i 1)] +/51,
Before proving Theorem 4.6 we prove some lemmas that will enable the construc
tion of a sequence of 5S;isaturated graphs.
Lemma 4.7
Let s > 3 and t > 2. Suppose G is a BSytsaturated graph that contains two tree
components Tx = Tff and T2 = (in the case that s = 3 or s = 4 one ofTi and T2
may be K2). If H = G {Ti,T2} and T is a BSytsaturated tree of order pi + p2 then
G' = H U T is a BSytsaturated graph where e{G') = e(G) + 1.
Proof: Let p = pi + p2. Since Tft and G are P^saturated it follows that G'
does not contain Bst. Let e G E(G'). In order to show that G' + e contians Bst
we will consider several cases. First, if e G E(T%t), then Tf_t + e contains BSyt since
Tf_i is PS;isaturated, hence G' + e contains BSyt. Now, since G is Â£>.^saturated, if
e G E(H) then G' + e contains BSyt. Finally, suppose that e has at least one endpoint
in V(H) and one in V(T%t). Notice that H U Tff is an induced subgraph of G'.
If G' + e does not contain BSyt, then by deleting pendant vertices not incident to e
it can be seen that H U + e des nt contain BSyt, since deleting vertices can
not create a copy of Bs t. This implies that G is not Â£>.^saturated, a contradiction.
Therefore G' is Â£>S)tsaturated. Finally, note that e(G) = e(H) + (pi 1) + (p2 1)
and e(G') = e(H) + {jp\ +p2 1), thus e(G') = e(G) + 1.
41
Lemma 4.8
Let s > 3 and t > 2. Suppose G is a BSytsaturated graph with a tree component Tft
wherep > bSyt [(s+2_1) (s + t 1)] + (s + t 1). Let F = [(s+2_1) (s + t 1)] T*t
such that F = p (s + t 1). If H = G T%yt, then G' = H U Ks+t\ U F is a
BSytsaturated graph where e{G') = e(G) + 1.
Proof: Note that e(G) = e(H) + p 1 and e(G') = e(H) + (s+2_1) + e(F). Since
F is a forest onp (s+t 1) vertices and [(s+2_1) (s + t 1)] components it follows
that e(F) = p (s+t 1) [(s+2_1) (s + t 1)]. Thus e(G') = e(H)+p = e(G) +1.
It remains to show that G' is 5S;tsaturated. Let e G E(GI). Notice that if e
is incident to Ks+ti then G' contains BSyt. First suppose that e G E(F), from the
observation following Lemma 4.1 it follows that G' + e contains BSyt. Next suppose
that e has both endpoints in V(H). Clearly, since G is 5S;isaturated G + e contains a
copy of BSyt such that V(BSyt) C V(H). Thus, G' + e contains a copy of BSyt. Finally,
suppose that e has one endpoint in H and one in F. Assume that G' + e does not
contain BSyt. Let T be the component of F incident to e. Let G = G'[H UT], Notice
G + e does not contain Bs t. Further since G = H U Tjt and G = H U T differ only
in the number of pendants adjacent to a vertex of highest degree in T and Tg t, it is
easy to see that G + e does not contain Bs t. Thus, G' is 5S;isaturated.
The transformation in Lemma 4.7 will be referred to as a tree exchange and the
transformation in Lemma 4.8 will be referred to a clique exchange. We are now ready
to prove Theorem 4.6.
Proof: Beginning with a forest F = qTSyt U Tft where q = _yyj 1 we will
build a sequence of 5S;isaturated graphs, G\,..., Gf, of size n yy to (s+2_1)r +
bSyt [(s+2_1) (s + t 1)] + /3 1 where e(Gj+i) = e(Gi) + 1 for 1 < i < f 1. Once
Gi is built use one of the following exchanges to build Gi+\.
1. If Gi contains two components Tff and then use a tree exchange to create
Gi\1
42
2. If Gi contains exactly one tree component and the tree has at least
b
S,t
s + t
2
(s + t 1)
+ (s + t 1)
vertices, then use a clique exchange to obtain Gi+\.
Lemmas 4.7 and 4.8 imply that when either a tree exchange or a clique exchange
is used, Gi+i is a Â£>S)tsaturated graph with e(Gi+1) = e(Gi) + 1. As long as there are
at least two tree components or there is a single tree component T in Gi such that
\T\ > bSyt [(s+2_1) (s +1 1)] + (s + t 1), one of the exchanges can be used to
build Gi+1 So the final graph built by the algorithm will have one tree component
of order less than bSyt [(s+2_1) (s + t 1)] + (s + t 1).
Since n = r(s + t 1) + bs,t [(S+2_1) (s +1 1)] + /3, it follows that upon
constructing Gi = (r l)Ks+ti U T*t that \T*t\ = bs,t [(s+2_1) (s + t 1)] +
(s + t 1) + /3. Thus another clique exchange can be used followed by tree ex
changes to produce rKs+ti U At this point it is easy to calculate q =
bs,t [(s+2 1) (s + t ~ 1)] + ft < bSyt [(s+2 1) (s + t ~ 1)] + (s + t 1). So the
algorithm will terminate with Gf = rKs+t_i U T%t. The size of Gf can be calculated
as follows:
e(Gf)
s + t 1
s + t 1
r + [n r(s + t 1) 1]
r + b.
's.t
s + t 1
(s + t 1)
+ p 1.
If the Erdos Sos conjecture is true for all brooms, then we can use Theorem 4.6
to show that for n sufficiently large, s > 4 and t > 2, spec(n, Bs>t) contains all values
from n
below.
to ex(n, Bs>t) c where c = c(s,t). We give an outline of the proof
Let n be expressed as n = r(s + t 1 ) + bSyt [(s+2 (s + t 1)] +/3, where f3 is a
constant such that 0 < [3 < s + t 1. The algorithm in the proof of Theorem 4.6 gives
43
a sequence of Â£>S;tsaturated graphs that contains graphs of each size from n
to (s+2_1)r + bs>t [(s+2_1) (s + t 1)] + fd 1. Let G be a Â£>S)tsaturated graph of
size (s+1~1)t' + bs>t [(s+2_1) (s +1 1)] + fd 1. From the Erdos Sos conjecture,
(n,BSyt) < h+*~2)ra. Now it is possible to bound ex(n,BSyt) e(G) as follows:
ex
ex(n,BSyt) e(G)
(s + t 2 )n
<
s + t 1
r + b.
's.t
s + t 1
(s + t 1)
+ p 1
<  t ~b^t(S+t~1) + (S+t1) X
Thus, for a fixed s and t the difference between ex(n,Bs,t) and e(G) is a constant,
dependent only on s and t, for all n sufficiently large.
Although Theorem 4.6 gives many values of m such that m G spec(n, Bs>t) it does
not give values such that m spec(n, Bs>t). However, the results of Chapter 5 imply
that there are values immediately preceding ex(n, Bs t) that are not in spec(n, Bs t)
for large classes of brooms.
4.3 Saturation Spectrum of B^t
In this section we improve on the results of the previous section for B3 t. We
begin by giving a characterization of Â£>3;tsaturated graphs.
Lemma 4.9
If G is a connected B3ytsaturated graph, then G is either
1. Kr, r
2. Ki>r, r > t + 2, or
3. has maximum degree t, order at least t + 3 and all vertices of degree less than t
form, a clique.
Proof: Kr with r < t + 2 and Ki r withr > t + 2 are clearly H3 tsaturated
graphs. Let G be a connected Â£>3;tsaturated graph. Notice that if G
44
must be a complete graph as adding any missing edge can not create a copy of B^t,
which has order t + 3.
Assume that G has a vertex, v, with d(v) > t + 1. Since, G is Â£>3;isaturated there
are no vertices in G at distance 2 from v, otherwise G would contain Â£>3;t. Since, G is
connected this implies that G = G[fVV]]. Notice that if d{v) = t + 1 then G = t + 2
and hence G = Kt+2.
Assume d(v) > t + 2 and let and w be distinct neighbors of v. If uw G E(G),
then u w and v together with the other t neighbors of v form a copy of _E>3t, since
G is Â£>3)tsaturated this can not happen. Since, the choice of u and w was arbitrary,
this implies that N(v) is an independent set. It follows that G is a star.
Finally assume that A(G) < t. If G has two nonadjacent vertices u and w with
d(u) < d(w) < t, then adding the edge uw can not create a copy of B3tt as no vertex
of degree t + 1 would be formed. It follows that all vertices of degree less than t must
form a clique. In particular if A(G) = t then G is a complete graph.
Now, we will provide examples from a family of graphs of the third type in
Lemma 4.9. The p power of a graph G is a graph Gp such that V(GP) = V(G) and
E(GP) = {uv : dc(u,v) < k}. Label the vertices of a cycle G& clockwise V\ to vand
let k and t be integers such that k > t + 3. Let Cfk be the  power of G& when t is
even. When t is odd let Cfk be the power of G& with additional edges
for 1 < i < [J. (See Figure 4.1). Notice that Ck is a tregular Â£>3)tsaturated graph
when t is even or k is even. When t is odd and k is odd Ck is a nearlytregular
Â£>3;tsaturated graph.
Faudree et al. characterized the graphs in SATfa, B% f).
Theorem 4.10 ([22])
For t > 2, every graph G G SATfa, B* t) is a forest of stars. If n (t +
3) L^J > 2, then exactly one of the stars is K2.
45
Figure 4.1: Some Â£>3;t saturated graphs.
Theorem 4.11
Let t G {2, 3} and n = q{t + 2) + r where 0 < r < t + 2 and q > 1. IfGe SAT(n, Â£>3t);
then G = qKt+2 U Kr and ex(n, B3>t) = +2) + Q
Proof: Let n = q(t + 2) + r where 0 < r < t + 2 and G be a graph with
G = qKt+2 U Kr. Note that G is Â£>3tsaturated, thus ex(n, Â£>3t) > g(*1>2) + Q Let
it be a Â£>3;tsaturated graph of order n and size at least g(*1>2) + Q The average
degree of H can be calculated as follows:
d(H) >
2d(
t+2
2
+ 2) + r
qit + 2)(f + 1) + r(r 1)
q(t + 2) + r
qit + 2)(t + 1) + r(t + 1) r(t + 1) + r(r 1)
(t + 1) +
= (t + 1) +
+ 2) + r
r{t + 1) + r(r 1)
q(t + 2) + r
r(r (f + 2))
q(t + 2) + r
Notice that since r < t+1 that r (i + 2) < 0. Hence, if < 1, then d(H) > t.
Notice that r(t + 1) r2 is maximized when r = LjT. Hence, r(t+ 1) r2 < < 4
46
when t = 3 and r(t + 1) r2 < < 2 when t = 2. Since q > 1, it follows that:
r(t + 1) r2 < (i + 2)g
r(t + 2) r r2 < (i + 2)g
r{t + 2) r2 < (f + 2)g + r
r((f + 2) r) < (t + 2)g + r.
Thus r^q{t+2)+r < 1 and d(H) > t. Lemma 4.9 implies that H contains a copy of
Kt+2. Suppose that H contains k copies of Kt+2 and let H1 = H kKt+2. Now we
can calculate the average degree of H1 as follows:
d(H') >
2 {{q~k)(
t+2
2
3)
(q k){t + 2) + r
(
(q k){t + 2) + r
(
(f + 1) +
(t + 1) +
(
r{t + 1) + r(r 1)
(q k){t + 2) + r
r(r (t + 2))
(
Similar to above if ^ly^]_2)+r < then h(iT) > i. Notice that if q = fc then H' has
fewer than t + 3 vertices and, by Lemma 4.9, must be complete. This implies that
H = Kt+2 U JLr. If q > k, then as before it follows that:
r(t + 1) r2 < (t + 2)(q k)
r(t + 2) r r2 < (t + 2)(g k)
r{t + 2) r2 < (t + 2)(g fc) + r
r((t + 2) r) < (t + 2)(g fc) + r.
Thus h(iT) > t, which is impossible since H1 has no components with average degree
more than t. Thus the only graph G such that G E SAT(n,B3 t) for t E {2,3} is
qKt+2 U Kr. m
47
Theorem 4.12
Let t > 2 and n = q(t + 2) + r where 0 < r < t + 2 and n > t + 3. If G E SAT(n, Â£>3;t)
then
e(G) =
(.Q 1)C
t+2'
2
t(t+2+r)
2
if r < 1 or r >t
otherwise,
and either G = qKt+2 Uifr or G = (q l)Kt+2 U H where H is a tregular (or nearly
regular) Bs^saturated graph.
Proof: Let G be a Â£>3tsaturated graph. If G contains a component Ki r with
r > t + 2 then the copy of Kcan either be exchanged for a tregular component or
the vertices can be added to a component of G with max degree t to produce a new
Â£>3;tsaturated graph with more edges than G. Thus, an extremal graph for Â£>3)t has
no component Ki>r. It follows from Lemma 4.9 that a Â£>3)textremal graph will only
have components that are complete or that have max degree t. Further, if G contains
a component on r vertices with max degree t that is not tregular (or nearly regular),
then the component can be exchanged for C* to produce a Â£>3;tsaturated graph with
more edges. Hence any component with max degree t in a H3 textremal graph will
be tregular (or nearly regular).
Now, suppose that G contains a collection of complete components that are of
order less than t + 2. Iteratively deleting a vertex from the smallest component in
the collection and adding it to the largest component, as a spanning vertex, in the
collection until the largest component is a complete graph of order t + 2 will produce
a graph with more edges than G. This process can be repeated until there is a single
complete component Kr where r < t + 1. If there is a component X in G that is
tregular (or nearly regular), then the vertices of Kr can be add to X to produce a
larger tregular (or nearly regular) component Y. Notice e{Kr U X) < e(Y).
Therefore, a H3;textremal graph on q{t + 2) + r vertices is either qKt+2 U Kr or
48
kKt+2 U H where H is a tregular (or nearly regular) graph on (q k)(t + 2) + r
vertices. It remains to show that k = q 1. By Lemma 4.9, each component of H
must have at least t + 3 vertices. Since r
that k ^ q. Now if k < q 1, then H can be replaced by Kr+1 U C'*g_fc_1)(t+2)+r, which
increases the size of the graph. Therefore k = q 1.
Finally, it is easy to verify that + (2) > (
t(t+2+r)
2
when r < 1
or r>t and q(t+22) + Q < (q 1) (*+2) +
t(t+2+r)
2
otherwise.
Now, we will show that there are values m immediately preceding ex(n, B3 t) such
that m ^ spec(n, B3>t).
Lemma 4.13
Let n and t be an integers such that t > 2 and n > 2{t + 2). If n = 0
(mod i + 2) and m E {ex(n, 53;t) [t + 1), ex(n, B3tt) t,..., ex(n, 1}; then
m fz spec(n, B3>t).
Proof: First note that from Theorem 4.12 that ex(n,B3yt) = (t+21'>ra. Let n =
(t+ 2) k and G be a Â£>3;tsaturated graph of order n and size at least n {t + 1).
It will be shown G contains at least k 1 copies of Kt+2 Notice that if G contains
k 1 copies of Kt+2 that the remaining t + 2 vertices must also form a clique. So, if
G contains at least k 1 copies of Kt+2 then G is the extremal graph. The average
degree of G can be calculated as follows:
d{G) >
it + l)(t + 2 )k 2(t + 1)
t + 1
k(t + 2)
2 (f + 1)
k(t + 2)
Notice that n > 2(t + 2) implies that k > 2, so t + 1 > t. Thus, we have
d(G) > t. Lemma 4.9 implies that the only component of a Â£>3;tsaturated graph with
average degree greater than t is Kt+2. It follows that G must contain a copy of Kt+2.
Let j be the number of copies of Kt+2 in G and let H = G jKt+2. Now, d(H) can
49
be calculated as follows:
d{H) >
(t + l)(f + 2 )k (t + l)(i + 2 )j 2 (t + 1)
t + 1
k(t + 2) j(t + 2)
2(t + 1)
(fcj)(f+ 2)'
Lemma 4.9 implies that h(hf) < t. This implies that 1> thus ^ j < l
Since, k and j are both positive integers it follows that j = k or j = k 1. In
either case G must be the extremal graph. Hence, the only H3)3saturated graph of
order n = 0 (mod t + 2) with at least fhhihl (t + 1) edges is the extremal graph.
In particular, if me {ex(n, B3t) [t + 1), ex(n, B3>t) t,..., ex(n, B3>t) 1}, then
m spec(n, B3>t). u
In a similar fashion to the previous lemma we will show that there is a gap in the
saturation spectrum for Â£>3)2 and h>3;3 when n = t + 1 (mod t + 2).
Lemma 4.14
Let n be an integer such that n > (t+2) + (t+l) and 2
and m E {ex(n, Â£>3;t) [t 1),..., ex(n, Â£>3)t) 1}; then m spec(n, B3tt).
Proof: Let n = (f+2)fc+(f+l) and note that Theorem 4.12 implies ex(n, B3yt) =
k(t+22) + Let G be a Â£>3;tsaturated graph of order n and size at least +
P+1) {t 1). It will be shown G contains at least k copies of Kt+2. Notice that if
G contains k copies of Kt+2, the remaining t + 1 vertices must also form a clique. So,
if G contains at least k copies of Kt+2, then G is the extremal graph. The average
degree of G can be calculated as follows:
d(G) >
k{t + 2)(t + 1) + (f + l)(t) 2(t 1)
k(t + 2) + (t + 1)
k(t + 2)(t + 1) + (f + 1 )(f + 1) (t + 1) 2(t 1)
k(t + 2) + (f + 1)
2 jt 1) + (t + 1)
k(t + 2) + (t + 1)
50
Notice that n > (t + 2) + (t + 1) implies that k > 1, so f + 1 > t for
t = 2 or t = 3. Thus, we have d{G) > t. Lemma 4.9 implies that the only component
of a Â£>3;tsaturated graph with average degree greater than t is Kt+2 It follows that
G must contain a copy of Kt+2. Let j be the number of copies of Kt+2 in G and let
H = G jKt+2. Now d(H) can be calculated as follows:
k(t + 2 )(t + 1) (t + l)(t + 2)j + (t + l)(t) 2 (t 1)
d{H) >
k{t + 2) j it + 2) + (t + 1)
k{t + 2 )(t + 1) (f + l)(t + 2)j + (f + 1 )(f + 1) (f + 1) 2 (f 1)
f + 1
k(t + 2) j(t + 2) + (t + 1)
2 (t 1) + (f + 1)
j)(t + 2) + (i + 1)
Lemma 4.9 implies that d(H) < t. This implies that (k^j(2)+(t+1) 1> or
4(fcj)+3 ^ W^en f = 2 and 5(.fc_^+4 > 1 when t = 3. In both cases fc j < 1. Since
fc and j are both positive integers it follows that j = k. In either case G must be the
extremal graph. Hence the only H3 tsaturated graph of order n = t + 1 (mod t + 2)
with at least n [t + 1) edges is the extremal graph.
In the following two sections we will completely determine the saturation spec
trum for Â£>3 2 and Â£>3 3.
4.3.1 Saturation Spectrum of Â£>3 2
Notice that every cycle Ck with Â£ > 5 is Â£>3)2saturated. A set of graphs in
SAT(n, H3;2) for 5 < n < 11 is given in Table 4.1.
Lemma 4.15
Let n be an integer and k = sat(n, Â£>3,2). If n > 12; then {k, k + 1, ...,Â£ + 3} G
spec(n,H3;2).
Proof: By Theorem 4.10 every graph G G SATfa, Â£>3 9) is a forest of
stars. Thus for n > 12 each graph in SAT(n, ^3,2) contains at least 3 stars, Â£\,... Â£3.
Let X = V(Ti) U U V(T3). Notice that by Theorem 4.10 at most one of the trees is
51
Table 4.1: Saturation Spectrum of Â£>3,2 for 5 < n < 11.
e(G) 5 6 7 8 9 10 11
4 k1a
5 C5 KltS k1a u k2
6 kauk1 c6 Kh6 k4A u k2
7 k4uk2 C7 K4,7 K\A u k2
8 None Cg K4,8 2 K1}4
9 K4UK3 None C9 k1i9 k4}4 u k1a
10 None k4 u K\A cw Khl0
11 None k4\jc5 k4 u k1a C\ 1
12 2K4 2K4 U K\ k4uc6 K4 U
13 2K4 U K2 k4uc7
14 None
15 2K4 U K3
K2 and the other trees have at least 5 vertices thus X > 12. Combining the vertices
two of the starts to create a larger star in G[X] creates a Â£>3,2saturated graph G1
with k + 1 edges. Repeating this procedure again so that G[X] contains a single start
yields Â£>3,2saturated graph G2 k + 2 edges. Now G2IX] can be exchanged for C\x\ to
create G3, clearly  G31 = k + 3.
52
Theorem 4.16
Let n > 5 and sat(71,83,2) 3)2) if and only if
n = 1,2 (mod 4) or
{f3,f2,ft} */n = 0 (mod 4),
m ^ <
{^} if n = Z (mod 4).
Proof: The proof follows from Lemmas 4.15, 4.13 and 4.14, and Table 4.1,
by induction on n. Let n > 12. First observe that if G G SAT(n 4, Â£>3)2), then
G U K4 G SAT(n, 53,2) Thus, adding a A4 to each graph in SAT(n 5, Â£>3,2) gives
83,2saturated graphs of each size from sat(n 4, Â£>3,3) + 6 to ex(n 4, Â£>3,3) + 6 when
n= 1,2 (mod 4). Notice ex(n 5, 83,3) + 6 = ex(n, 83;3).
If n = 0 (mod 4), then adding a A4 to each graph in SAT(n 4, Â£>3)2) gives
^3,2saturated graphs of each size from sat(n 4, Â£>3,2) + 6 to ex(n, Â£>3,2) = y1 except
y1 1, y1 2 and y1 3. If n = 3 (mod 4) then adding a A4 to each graph in
SAT(n 4, Â£>3,2) gives 83)2saturated graphs of each size from sat(n 4, Â£>3,2) + 6 to
ex(n, Â£>3,2) = except ^yy. If n = 0 (mod 4) Lemma 4.13 implies that there
are no Â£>3)2saturated graph of size iy 1, iy 2 and y1 3 and if n = 3 (mod 4) ,
Lemma 4.14 implies that there are no 83)2saturated graph of size yyi.
Notice that
sat(n, Â£>3,2)
sat(n
n n + 3 n 4 n + 3 4
5 5
n + 3 + n + 3 4
5 5
> 3.
Thus Lemma 4.15 implies there are 83;2saturated graphs of each size from sat(n, Â£>3,2)
to sat(n 5, Â£>3,2) T 10.
53
4.3.2 Saturation Spectrum of B3;3
Let C2k denote the graph obtained from by adding an edge between every
pair of antipodal vertices. Let C'2k+l be the graph obtained by subdividing a cycle
edge of C2k. Similarly, let C2k denote the graph obtained by subdividing a cycle edge
of C2k_2 twice. It is easy to verify that each of these graphs is L^saturated, when
the graphs have order at least 6.
Lemma 4.17
Let n be an integer and k = sat(n, B3>3). If n > 22, then {k, k + 1,..., k + 5} G
spec(n, B3)3).
Proof: By Theorem 4.10 every graph G G SAT(n, B3 3) is a forest of stars.
Thus, for n > 22 each graph in SAT(n, B3>t) contains at least 4 starsv, T4,... T4. Let
X = V{Ti) U U R(T4). Notice that by Theorem 4.10 at most one of the trees is
K2 and the other trees have at least 6 vertices thus X > 20. Combining the vertices
two of the starts to create a larger star in G[X] creates a Â£>3)tsaturated graph G\
with k + 1 edges. Repeating this procedure until G[X\ contains a single start yields
Â£>3;3saturated graphs G2 and G3 with k + 2, and k + 3 edges respectively. Now G3[X]
can be exchanged for K4 U U Ki,xn to create G4, clearly G4 = k + 4. By
construction, every component of G4 has at least 2 vertices, this implies that adding
any edge between fd4 and another component creates B3>3 thus G4 is L^saturated.
Finally the two stars in G4 may be combined to form a larger star and create G5.
Theorem 4.18
Let m be an integer and n be an integer such that n > 17. If sat(n, Â£>3,3) < m <
ex(n, B3>3), then m G spec(n, B3>3) if and only if n = 1,2,3 (mod 5) or
54
I {2n 1,2n 2, 2n 3, 2n 4} if n = 0 (mod 5)
m ^ <
{2n 3,2n 4} ifn = 4 (mod 5).
Proof: The proof follows from Lemmas 4.17, 4.13 and 4.14, and Table 4.2,
by induction on n. Let n > 22. First observe that if G E SAT(n 5, Â£>3)3) then
G U K5 e SAT(n, Â£>3)3). Thus, adding a K5 to each graph in SAT(n 5, Â£>3)3) gives
Â£>3)3saturated graphs of each size from sat(n 5, B3 3) + 10 to ex(n 5, B3 3) + 10,
notice ex(n 5, B3 3) + 10 = ex(n, B3 3), when n = 1,2, 3 (mod 5).
If n = 0 (mod 5), then adding a K5 to each graph in SAT(n 5, B3 3) gives B3>3
saturated graphs of each size from sat(n 5, Â£>3,3) + 10 to ex(n, B3>3) = 2n except
2n 1,2n 2, 2n 3, and 2n 4. If n = 4 (mod 5), then adding a K5 to each graph
in SAT(n 5, Â£>3,3) gives 53,3saturated graphs of each size from sat(n 5, Â£>3,3) + 10
to ex(n, B3>3) = 2n 2 except 2n 3 and 2n 4. If n = 0 (mod 5) Lemma 4.13
implies that there are no Â£>3;3saturated graph of size 2nl,2n 2,2n 3, and 2n 4
and if n = 4 (mod 5) Lemma 4.14 implies that there are no Â£>3;3saturated graph of
size 2n 3 and 2n 4 respectively.
Notice that
sat(n, B3>3) sat(n 5, B3>3)
n
n + 4
n 5
n + 4 5
6
= 5
> 4.
n + 4 + n + 4 5
6 6
Thus Lemma 4.17 implies there are Â£>3;3saturated graphs of each size from sat(n, Â£>3,3)
to sat(n 5, ^3,3) + 10.
55
e[C
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Table 4.2: Saturation Spectrum of Â£>3;3 for 17 < n < 21.
17 18 19 20 21
K2 U U Ki^e
Ki'g U Ki,7 376i,b
76;L,16 76i,b U 76i,n 2T6i,b U T6i,6 762 U 376i,b
k4 uk1>6 uk1>5 Khlr 76i,b U76i,i2 2T6i,b UT6i,7 T62 U 276i,b U76i,6
K4 U T6i, 12 K4 U 2K1>6 76i,i8 76i,b U76i,is 2T6i,b UT6i,8
Cg U Ki^io K4 U 761,13 764 U T6i,7 U 76i,6 76i,i9 76i,b U76i,i4
C*UKh8 Cg U 761,11 764 U76i,i4 764 U 2T6i,7 to O
76b U 76i,n Cg U 76i,g Cg U 76i,i2 764 U 76i,ib 764 U T6i,io U 76i,b
k5uk4uk2u k1}6 K5UK1>12 Cg U T6i,io 2K4 U 2Ki,5 764 U 76i,i6
KÂ§ U K4 U 3K4 U i^i,5 76b U 76i,i3 76b U T6i,7 U T6i,6 2K4 U U Ki}q
Cl6 U KX 76B U 764 U Klys 3764 U 76i,i6 76b U76i,i4 76b U2T6i,7
C[7 K2 U C{6 i^5 U i^4 U i^l,9 3K4 u i^l,7 76b U76i,ib
2K5UK1>6 2K4 U C(0 76b U Cg U T6i,7 76b U764 U76i,io i^5 U i^4 U 2Ki,5
k5 u C12 276b U T6i,7 Ks U K16* 76b U Cg U 76i,8 U K4 U Ki}h
K5 U K4 U Cg 76b U 763 U Cl0 276b U76i,8 3^4 U Cq U K2 76b U Cg U 76i,9
2K5 U C* U Ki 76b U T64 U C'g Kq U K2 u c\2 276b U T6i,g U Cg U K\^
276b U C'r 2K% U K2 U Cq 76b U C(4 5764 276s U76i,io
376b U K2 276b U C'8 76b U C*4 76b U C42 U 763 C'21
276b U C 276b U 763 U Cg 76b U C4B 276b U 764 U 76i,6
376b U 763 276b U Cg 276b U 2764 U 762 76b U C(6
None 276b U C40 i^5 U C^Q
None 276b U C40 376b U 76i,b
3K5 U K4 None 276b U CP
None 376b U 764 U 762
None 376b U C'
None 376b U Cg
476b 4K5 U Ki
56
CHAPTER 5
GAPS IN THE SATURATION SPECTRUM
In this chapter, we give general results showing that for given graphs, there are
particular values e, between sat(n, G) and ex(n, G) for which there can not exist
Gsaturated graphs having e edges. This is joint work with Ron Gould, Paul Horn,
and Michael Jacobson. As noted in Chapter 2, a double star Sa>b is the tree of order
a + b with a vertex of degree a adjacent to a vertex of degree b.
Definition 5.1
A tree Tg of order Â£ is embeddable if every connected graph G of order at least Â£ with
d(G) > Â£ 3 and 8(G) > _J contains a copy of'Tg.
The following result was obtained by Erdos and Gallai [17] and is implicit in the
work of Dirac (cf. [13].)
Theorem 5.2
If G is a connected graph with minim,um, degree 8 and order at least 28 + 1, then G
contains a path on at least 28 + 1 vertices.
Since 2 _J + 1 > Â£, we obtain the following corollary.
Corollary 5.3
Paths are embeddable.
A tree T of order Â£, T yt having a vertex that is adjacent to at least [J
leaves will be referred to as a scrubgrass tree. The set of scrubgrass trees of order
Â£ will be denoted SGg. We will show that scrubgrass trees are embeddable; first we
give the following lemma.
57
Lemma 5.4
Let Fg be a forest of order Â£ and G be a graph with 8(G) > Â£ 1. If v E Fg and u E G
then there is an embedding of Fg in G such that u is mapped to v.
Proof: We will prove a more general result. Specifically, we will show that a
forest, Fg, on Â£ vertices can be embedded into a graph, G, with minimum degree Â£1,
so that any set of vertices, X, containing exactly one vertex from each component of
Fg can be mapped into any set of X vertices of G.
Notice that there are 2 forests on 2 vertices, namely P2 and 2Kg. In both cases,
it follows that the forest can be embedded into any graph G with 8(G) > 1. Further,
this can be done having any vertex of G correspond to either vertex of P2 and any 2
vertices of G correspond to the vertices of 2Kg. Hence the result holds when Â£ = 2.
Assume the result holds for every forest of order at most Â£ 1. Let Fg be a forest
of order Â£ and X be a set of vertices of Fg containing exactly one vertex from each
component of Fg. Additionally, choose v E X. Let G be a graph with 8(G) > Â£ 1 with
a vertex u E G. Fg v is a forest, Fgi, of order Â£1, and G u has 8(G u) > Â£ 2.
Set Y = X {u}. By the induction hypothesis, Fgi can be embedded into G u
so that the neighbors of v in Fgi are mapped to neighbors of u in G u and the
vertices in Y are mapped to other vertices in G u. This embedding of Fg1 into
G u together with u form an embedding of Fg in G. Since the choice of v and u
was arbitrary, it follows that this embedding satisfies the condition of mapping any
set of vertices, X, containing exactly one vertex from each component of Fg into any
set of X vertices of G.
We are now ready to prove that scrubgrass trees are embeddable.
Theorem 5.5
Scrubgrass trees are embeddable.
58
Proof: Let Tg e SGg and suppose that v E Tg is adjacent to at least _J leaves.
Let G be a graph with 8(G) > _fj and d(G) > i 3. Suppose that there is vertex
u in G such that d(u) >11. G u is a graph with 8(G u) > _J 1. Notice
the forest obtained by removing v and all the leaf neighbors of v from Tg has order at
most i _J 1 < _J. Thus, by Lemma 5.4, the forest may be embedded into G u
so that the nonleaf neighbors of v correspond to neighbors of u. Since d(u) > t 1,
there are at least [J neighbors of u unused in this embedding. It follows that G
contains Tg.
Now, suppose that A(G) = i 2 and let u E G such that d(u) = i 2. Since Tg is
not a star, there is some vertex, w, in Tg so that d(v, w) = 2. There are Â£1 vertices in
N[u], which implies there is a vertex x E G N[u\. More specifically, there is a vertex
x E G such that dc(u,x) = 2. Choose a vertex x' such that x' E Ng(u) Pi Ng(x) and
let w' be the common neighbor of v and w in Tg. Now, removing v along with all the
leaf neighbors of v and w' from Tg creates a forest T'e with at most 2 < _J 1
vertices and G {u^x'} is a graph with minimum degree at least [J 2. Lemma
5.4 implies that Tjj can be embedded into G {u, x'} so that the neighbors of v in Tg,
other than w', are neighbors of u in G and neighbors of w' in Tg, other than v, are
neighbors of x' in G. Therefore there in an embedding of Tg in G.
The remainder of the results in this chapter will expand on the properties of the
class of embeddable trees and use these results to show there is gap in the saturation
spectrum of all embeddable trees in Theorem 5.8. By applying Theorems 5.3 and 5.5
we obtain Corollary 5.9, which states that saturation spectrum of scrubgrass trees
and paths have a gap.
59
Lemma 5.6
Let Te be an embeddable tree on Â£ > 6 vertices. If G is a Tgfree graph and there is
no set of Â£ 1 vertices that induce at least _^J edges, then
Â£ d(v) < (f 2)\G\
 2
2~
vev(G) L 1
Proof: First note that every graph of order at most Â£ 2 is Tgfree and does
not contain a set of Â£ 1 vertices. Let G < Â£ 2 with Â£ > 6. The degree sum of G
is at most
G(Gl)<(d2)(Gl)
= (d2)G {Â£ 2)
< {Â£ 2)G 2 Â£~2
Hence, d(n) < {Â£2)G 2 _^J for every graph G such that G < Â£2.
If  G  = Â£ 1, then the result follows from the condition that no set of Â£ 1 vertices
induce more than 1_^J edges.
Thus, any counterexample to the theorem must have order at least Â£. Let G be a
vertex minimal counterexample to the statement; that is, suppose G is that smallest
order graph that is T^free and no set of Â£ 1 vertices induce more than _^J
edges and
d(v) > (/:' 2)G
 4
2
vev(G) L 1
If G is disconnected, then there is some component X of G such that d(G) <
d(G[X]), hence G[X] is a smaller counterexample. Thus we may assume that G is
connected.
Suppose there is a vertex u E V(G) such that d(u) < _J. Notice that since G u
is a subgraph of G, it is T^free and does not contain a set of d 1 vertices that induce
more than edges. Now we calculate the degree sum of G u as follows:
60
Â£2
2
2
1
Â£ d(y) > (Â£ 2)\G\ 2
veV{Gu)
> (Â£ 2)\G\ 2
= (Â£2)\Gu\
Â£2
2
(Â£2)
2
Â£2
2
Thus G u is a smaller order counterexample than G. Hence we may assume
that 5(G) > [J. Finally, note that d(G) > (Â£ 2) py J > (Â£ 3). Therefore,
G contains every embeddable tree on Â£ vertices, a contradiction.
Lemma 5.7
Let T be a tree on Â£ vertices which is not Ahy_i; and G be a graph on Â£ vertices
consisting of a with at most L^J edges removed, having a single pendant edge
adjacent to one of the vertices. Then there is an embedding of T into G.
Proof:
We prove the slightly stronger statement: Let z* G V(T) such that all but one
of the neighbors of z* are leaves, and which has at most L^J leaf neighbors. Note
that in any tree that is a nonstar, there are always at least two vertices all of whose
neighbors except one are leaves, and at least one of these vertices must be adjacent
to at most _yrJ leaves. Denote with x G V(G) the neighbor of the pendant vertex
of G. We prove that there is an embedding of T, so that z* maps to x.
Inspection quickly verifies that this holds for 4 < Â£ < 5. (Note that the statement
is false if _yy^J is replaced by ~yy^~ for Â£ = 3, so our statement is best possible.) We
now assume Â£ > 6 and proceed by induction.
Let H be the graph formed by removing s < L^J edges from so that
G = H + e, where e is the pendant edge. Also, let x denote the vertex of the H
incident to the pendant edge in G. Note that since 2 s < Â£ 2, there are at least
61
two vertices of H not incident to any removed edges, at least one of these vertices is
not x, denote it by y.
Now let z G T be an internal vertex of T incident to only one nonleaf and incident
to as many leaves as possible, and z* be such an internal vertex incident to as few
as possible. Suppose z is incident to t leaves. Consider G' = G ({y} U L) where
L consists of t vertices of G {x} which are incident to as many removed edges as
possible. In particular, note that L is incident to at least min{t, s} removed edges,
and hence G' consists of H1, which is obtained by removing at most s min{t, s}
edges from JC_t_2, and the pendent edge.
Let T' be the subtree of T with z and its t leaf neighbors removed. We proceed
by showing that G' contains a copy of T', with z* G T' as x, so that we can add back
on z and the corresponding leaves by mapping z to y and the corresponding leaves
to the remaining vertices of H. Such an embedding exists by induction, unless one
of two things occur: T' is a star or z* is adjacent to more than leaves in T'.
However, if such an embedding is achievable by induction we need only verify that
the one internal neighbor of z, which will be called z', is not mapped to the pendant
edge. If z' is mapped to the pendant edge then z' must also be the unique internal
neighbor of z* and z' must have degree 2 in T. It follows that T' is a star, which is
impossible since an embedding of T' is achievable by induction.
Finally consider the two exceptional cases. If T' is a star id1^_t_2, note that T is
either a double star or two stars connected by a path of length two and hence there
are most three internal vertices and two with leaves. One of these, z, has at least
~^~ = _^J leaves. Thus i > s, which implies that H1 is a complete graph. Thus
G' is composed of iOt2 with a pendant vertex, and it is easy to find an embedding
of idiy_t_2.
Now suppose z* has k leaves for some k > 0, and the H1 is not complete (because
62
if it were, wed be done). In this case G' has at most
Â£2 t = Â£22t Â£tl{tl)2
(N l (N 1 (N
missing edges. Thus, there are at least t + 1 dominating vertices in H', and even
after removing t 1 of these dominating vertices, the resulting G" will have at most
et~1(t1)2 = \G \~2 missing edges in H". Now since dT{z*) < dT{z), it follows
that k < _^J Moreover if k = _^J, then T' is a star (hence we are done by the
previous case). Thus k < _^J, and after removing up to t 1 leaves from z* in T'
to form T", z* is adjacent to at most
d4
2
(t1)
Â£ 2t 2
2
2
leaves. This implies that a sufficient number of leaves adjacent to z* in T' may be
removed so that the induction hypothesis may be used to find an embedding of the
resulting tree. This embedding can be augmented to an embedding of T in G by
mapping the leaves removed from z* in T' to the dominating vertices in H' extending
to an embedding of T in in G in the obvious way.
Theorem 5.8
Let Tg be an embeddable tree on t > 6 vertices. If G is Tgsaturated with G = 0
(mod I 1) and G is not a union of copies of Kg_i, then
Â£(C) < hh
fl
Â£2
2
Proof: There is a component S of G which is not a copy of Kg_g. Note that
this implies Sj yt Â£ 1. It will be shown that G[S] satisfies the hypothesis of Lemma
5.6. Since G is T^saturated, it follows that G[S] is T^free. If Sj < Â£ 2, then there
is not a set of Â£ 1 vertices in G[S], Suppose that Sj > Â£ and there is a set of
vertices X in G[S] that induce at least _yy^J edges. Since G[S] is connected,
there is an addition vertex in S that is connected to G[X], Thus Lemma 5.7 implies
63
that G[I U {u}] contains every nonstar tree of order Â£. Therefore G[S] satisfies
the hypothesis of Lemma 5.6. Hence J2veV(S) d(v) < (Â£ 2)S' 2 _yy^J and any
component S that is not a copy of JGi has degree sum at most {Â£ 2)S' 2 _^J
Let X be the vertices of G that are in a JGi component and Y = V(G) \ X. It
follows that the degree sum of G can be bounded as follows:
d(v) = +
i>ev(G) vex veY
< (Â£ 2)\X\ + (Â£ 2)\Y\ 2
< (Â£2)\G\ 2
Â£2
2
Â£2
2
From the proof of Theorem 5.8, it is easy to see that when G = 0 (mod Â£ 1)
the extremal graph is a union of copies of idri Hence, as an immediate corollary to
Theorem 5.8, we obtain the following result.
Corollary 5.9
Let TÂ£ be a path or scrubgrass tree on Â£ > 6 vertices and n = G = 0 (mod Â£1) and
m be an integer such that 1
in spec(n,TÂ£). Hence there is a gap in spec(n,TÂ£).
64
CHAPTER 6
FUTURE WORK
The work in this thesis has lead to many additional problems in the area of graph
saturation. In this chapter we will briefly discuss some of these problems.
Theorem 2.29 gave the structure of unicyclic graphs that are 2Pfcsaturated; a
disjoint union of these graphs gives an upperbound on sat(n, 2Pk).
Problem: Determine sat (n,2Pk).
More generally, it would also be interesting to know sat(n,tPk). Theorem 2.32
gave the value of sat(n, 3P3). It may be possible to use the technique in the proof of
Theorem 2.32 to find sat(n,4P3) or sat(n, 5P3). However, in general it infeasible to
brute force search for values of sat(3t, tPs) when t is large.
Problem: Determine sa.t(3t,tPs).
In Chapter 3, it was shown that there are no gaps in the saturation spectrum for
stars.
Problem: Determine the set of trees T such that if T Â£ J, then there is no gap in
the saturation spectrum for T.
Theorem 3.10 showed that there is some constant c(k) such that there are no gaps
in the saturation spectrum for Pk at values less than ex(n, Pk) c{k). Corollary 5.9
showed that there is a gap in the saturation spectrum for Pk from ex(n, Pk) +1
to ex(n, Pk) 1 when n = 0 (mod k 1).
Problem: Determine the minimum value of c{k). What is spec(n, Pk)l
The results of Chapter 4 and Chapter 5, show that the saturation spectrum for
many brooms has a similar structure to the saturation spectrum for paths. Which is
to say that there is a long continuous interval of values in the saturation spectrum
with the only possible gaps occurring within some constant, which depends on the
order of the path or broom, of the extremal number.
65
Problem: Determine the set of trees T such that if T G J, then the only gaps in
spec(n, T) occur after ex(n,T) c(Tj).
This problem leads to the following related problem.
Problem: Determine the set of trees T such that if T G J, then spec(rr, T) contains
gaps near sat(n,T).
In Chapter 5 it was shown that paths and scrubgrass trees are embeddable and
hence the saturation spectrum for these trees contains a gap. It is interesting to note
that the gap from Corollary 5.9 is not as large as the gap in the saturation spectrum
for P5, P6, B3>2, and 53)3.
Problem: Adapt techniques from Chapter 5 to improve the size of the gap.
Since a t 2 regular graph does not contain a star on l vertices it is easy to see
that stars are not embeddable.
Problem: What trees are embeddable?
It is interesting to note that if a tree is embeddable, then that Erdos Sos Con
jecture holds for that tree. Thus, it may be quite difficult to determine the complete
set of embeddable trees.
The results in Chapter 4 for Â£>3 t showed that there is a gap in spec(n, B3>t) when
n = 0 (mod \B3>t\ 1). Additionally, in Chapter 5 it was shown that there is a gap
in the saturation spectrum for embeddable trees of order l when n = 0 (mod l 1).
Theorems 2.36, 2.37, 4.16, and 4.18 show there is also a gap in the saturation spectrum
for T when n = 1 (mod Tj 1) and T e {P5, P6, B3>2, Â£>3,31
Problem: Is there a gap in the saturation spectrum of all paths and brooms of order
t when n = 1 (mod i 1)? What trees have gap in the saturation spectrum when
n = 1 (mod Z 1)?
Problem: Can the techniques of Chapter 5 be applied to determine if there is a gap
in the saturation spectrum of embeddable trees with order Â£ when n ^ 0 (mod Â£ 1).
66
It would be interesting to study the saturation spectrum of graphs that are not
trees. In particular, there are families of graphs for which both the saturation number
and extremal number is known, but the saturation spectrum is not known. These
graphs include, some cycles, unions of complete graphs, generalized friendship graphs,
and complete multipartite graphs.
Problem: Determine the saturation spectrum for the graphs mentioned above.
67
REFERENCES
[1] M. Ajtai, J. Komlos, M. Simonovits, and E. Szemeredi. On the approximative
solution of the ErdosSos conjecture on trees, (manuscript).
[2] M. Ajtai, J. Komlos, M. Simonovits, and E. Szemeredi. The solution of the
ErdosSos conjecture for large trees, (manuscript).
[3] M. Ajtai, J. Komlos, M. Simonovits, and E. Szemeredi. Some elementary lemmas
on the ErdosT. Sos conjecture for trees, (manuscript).
[4] Noga Alon, Lajos Ronyai, and Tibor Szabo. Normgraphs: variations and appli
cations. J. Combin. Theory Ser. B, 76(2):280290, 1999.
[5] Kinnari Amin, Jill Faudree, Ronald J Gould, and Elzbieta Sidorowicz. On the
non(p l)partite Kpfree graphs. Discussiones Mathew,aticae Graph Theory,
33(1):923, 2013.
[6] P. Balister and A. Dogan. On the edge spectrum of saturation number for paths
and stars. Private communication.
[7] Curtiss Barefoot, Karen Casey, David Fisher, Kathryn Fraughnaugh, and Frank
Flarary. Size in maximal trianglefree graphs and minimal graphs of diameter
2. Discrete Math., 138(13):93 99, 1995. 14th British Combinatorial Conference
(Keele, 1993).
[8] Tom Bohman, Maria Fonoberova, and Oleg Pikhurko. The saturation function
of complete partite graphs. J. Comb., 1(2): 149170, 2010.
[9] J. A. Bondy and M. Simonovits. Cycles of even length in graphs. J. Combina
torial Theory Ser. B, 16:97105, 1974.
[10] Neal Bushaw and Nathan Kettle. Turan numbers of multiple paths and equibi
partite forests. Combin. Probab. Comput., 20(6):837853, 2011.
[11] Gary Chartrand, Linda Lesniak, and Ping Zhang. Graphs & digraphs. CRC
Press, 2010.
[12] Guantao Chen, Jill R. Faudree, Ralph J. Faudree, Ronald J. Gould, Michael S.
Jacobson, and Colton Magnant. Results and problems on saturation numbers for
linear forests. Bulletin of the Institute for Combinatorics and its Applications,
75:2946, 2015.
[13] G. A. Dirac. Some theorems on abstract graphs. Proc. London Math. Soc. (3),
2:6981, 1952.
68
[14] Paul Erdos. Extremal problems in graph theory. Proc. Sympos. Sm,o!enice,
13(2):2936, 1963.
[15] P. Erdos. Some recent results on extremal problems in graph theory. Results.
In Theory of Graphs (Internat. Sympos., Rome, 1966), pages 117123 (English);
pp. 124130 (French). Gordon and Breach, New York; Dunod, Paris, 1967.
[16] P. Erdos. On some new inequalities concerning extremal properties of graphs. In
Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 7781. Academic Press,
New York, 1968.
[17] P. Erdos and T. Gallai. On maximal paths and circuits of graphs. Acta Math.
Acad. Sci. Hungar, 10:337356 (unbound insert), 1959.
[18] P. Erdos, A. Hajnal, and J. W. Moon. A problem in graph theory. Amer. Math.
Monthly, 71:11071110, 1964.
[19] P. Erdos and M. Simonovits. A limit theorem in graph theory. Studia Sci. Math.
Hungar, 1:5157, 1966.
[20] P. Erdos and M. Simonovits. An extremal graph problem. Acta Math. Acad.
Sci. Hungar., 22:275282, 1971/72.
[21] P. Erdos and A. H. Stone. On the structure of linear graphs. Bull. Amer. Math.
Soc., 52:10871091, 1946.
[22] Jill Faudree, Ralph J Faudree, Ronald J Gould, and Michael S Jacobson. Satu
ration numbers for trees. Electron. J. Combin, 16(1), 2009.
[23] Jill R Faudree, Ralph J Faudree, and John R Schmitt. A survey of minimum
saturated graphs. Electron. J. Combin, 18:36, 2011.
[24] R. J. Faudree and R. H. Schelp. Path Ramsey numbers in multicolorings. J.
Combinatorial Theory Ser. B, 19(2):150 160, 1975.
[25] Ralph Faudree, Michael Ferrara, Ronald Gould, and Michael Jacobson. tKp
saturated graphs of minimum size. Discrete Math., 309(19):58705876, 2009.
[26] Zoltan Fiiredi and Miklos Simonovits. The history of degenerate (bipartite)
extremal graph problems, 2013.
[27] Ronald J. Gould, Wenliang Tang, Erling Wei, and CunQuan Zhang. The
edge spectrum of the saturation number for small paths. Discrete Math.,
312(17):26822689, 2012.
[28] L. Kaszonyi and Zs. Tuza. Saturated graphs with minimal number of edges. J.
Graph Theory, 10(2):203 210, 1986.
[29] Janos Kollar, Lajos Ronyai, and Tibor Szabo. Normgraphs and bipartite Turan
numbers. Combinatorica, 16(3):399406, 1996.
69
[30] G. N. Kopylov. Maximal paths and cycles in a graph. Dokl. Akad. Nauk SSSR,
234(1): 1921, 1977.
[31] T. Kovari, V. T. Sos, and P. Turan. On a problem of K. Zarankiewicz. Collo
quium Math., 3:5057, 1954.
[32] Bernard Lidicky, Hong Liu, and Cory Palmer. On the Turan number of forests.
Electron. J. Combin., 20(2):Paper 62, 13, 2013.
[33] Wolfgang Mader. 1faktoren von graphen. Mathematische Annalen, 201(4):269
282, 1973.
[34] Willem Mantel. Problem 28. Wiskundige Opgaven, 10(6061):320, 1907.
[35] Andrew McLennan. The ErdosSos conjecture for trees of diameter four. J.
Graph Theory, 49(4):291 301, 2005.
[36] Oleg Pikhurko. Results and open problems on minimum saturated hypergraphs.
Ars Combin., 72:111127, 2004.
[37] A. F. Sidorenko. Asymptotic solution for a new class of forbidden rgraphs.
Combinatorica, 9(2):207215, 1989.
[38] M. Simonovits. A method for solving extremal problems in graph theory, stability
problems. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 279319.
Academic Press, New York, 1968.
[39] Paul Turan. On an extremal problem in graph theory. Mat. Fiz. Lapok, 48(436
452)437, 1941.
70
