SOME EXTENSIONS OF GRAPH SATURATION TO EDGE COLORED,
ORIENTED, AND SUBDIVIDED GRAPHS
by
Craig M. Tennenhouse
Master of Arts, University of Colorado, 2001
A thesis submitted to the
University of Colorado Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
2010
This thesis for the Doctor of Philosophy
Date
Tennenhouse, Craig M. (Ph.D., Applied Mathematics)
Some Extensions of Graph Saturation to Edge Colored, Oriented, and Subdi
vided Graphs
Thesis directed by Professor Michael S. Jacobson
ABSTRACT
Extremal Graph Theory is the particular subfield of Graph Theory con
cerned with maximizing and minimizing certain parameters associated with
graphs and digraphs. Beginning with Mantel [46] and Ramsey [52], the study
of extremal graphs was extended by Turan [56] into edgemaximum clique free
graphs. Similar problems, particularly those in this thesis, are therefore referred
to as Turan type problems.
Erdos, Hajnal, and Moon [21] generalized Turans result even further, ini
tiating the study of graph saturation. A graph H is Gfree if it contains no
subgraph isomorphic to G. H is Gsaturated if it is edgemaximally Gfree.
Similarly, given a family T of graphs, H is Tsaturated if it is Gfree for every
graph G in T but the addition of any edge from the complement of H cre
ates some graph in T. Erdos, Hajnal, and Moon characterized, in particular,
edgeminimum edgemaximally clique free graphs on a fixed number of vertices.
Various others have characterized smallest edgemaximally Gfree graphs for
other classes of graphs G. In this thesis the concept of saturation is extended
to oriented graphs, characterizations of extremal interval graphs and interval
bigraphs are offered, minimal Tsaturated graphs are determined where T is a
family of subdivided graphs, a new saturation parameter on edgecolored graphs
is introduced, and impartial and partizan games related to oriented graph sat
uration are examined.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed
DEDICATION
This thesis is dedicated to my father Don, who always told me to do good, and
my daughters Ceili and Hadassah, who give me a reason to.
ACKNOWLEDGMENT
I would first like to thank my adviser, Michael S. Jacobson, for guiding me
from being interested in mathematics to actually engaging in mathematics. I
would also like to give credit to the collaborators with whom Ive worked on this
and other material over the past few years, and have mentioned in the following
pages. Lastly, and certainly most importantly, I thank my wife, Laura, for her
infinite patience, love, and support. I could not have accomplished this without
her.
CONTENTS
Figures ........................................................... ix
1. Introduction........................................................ 1
1.1 Prologue.......................................................... 1
1.2 Notation.......................................................... 2
1.3 Background........................................................ 6
2. Oriented Graph Saturation.......................................... 13
2.1 Introduction..................................................... 13
2.2 Motivation for extension to oriented graphs ..................... 13
2.3 Existence of saturated oriented graphs........................... 14
2.4 Results.......................................................... 18
2.5 Some Upper Bounds................................................ 24
2.6 The minimum order of a Dsaturated oriented graph................ 27
2.7 Future directions................................................ 29
3. Maximal NonInterval Graphs and Bigraphs........................... 30
3.1 Introduction..................................................... 30
3.2 EdgeMaximal NonInterval Graphs................................. 31
3.3 EdgeMaximal NonInterval Bigraphs............................... 33
3.4 EdgeMaximal Split NonInterval Graphs........................... 43
3.5 Other Examples................................................... 45
4. Subdivided Graph Saturation........................................ 48
vii
4.1 Introduction
48
4.2 Cycles.............................................................. 49
4.2.1 History .......................................................... 49
4.2.2 t < 6............................................................. 49
4.2.3 General Bounds.................................................... 64
4.3 Complete Graphs.................................................... 76
5. EdgeCritical G, H Colorings........................................ 85
5.1 Introduction........................................................ 85
5.2 Kneser Graphs....................................................... 86
5.3 Some Results........................................................ 89
6. Conclusion and Futher Directions.................................... 96
6.1 Oriented Graph Saturation........................................... 96
6.2 Maximal NonInterval Graphs and Bigraphs............................ 98
6.3 Subdivided graph saturation......................................... 99
6.4 EdgeCritical G, H Colorings ...................................... 100
References.............................................................. 102
viii
FIGURES
Figure
1.1 The unique graph realizing sat(8, K6).................................. 8
1.2 The unique smallest 3AVsaturated graph on 12 vertices.................. 8
1.3 The unique smallest Ab^saturated graph on 14 vertices................. 9
1.4 A Pq saturated graph.................................................. 10
2.1 G with edges xy and xz, G' with edge x'z' and nonedge x'y1, and G*
with edge x*z* and nonedge x*y*................................... 14
2.2 The oriented graph Hc,a............................................... 15
2.3 Cut vertices v',v* and noncut vertices w', w* in HGa F............. 16
2.4 The union of Ha,a with isolated vertices.............................. 19
2.5 The smallest P3saturated oriented graph on 7 vertices................ 19
2.6 A P5saturated oriented graph......................................... 20
2.7 A A'1(3i3)saturated oriented graph................................... 23
2.8 A transitive tournament saturated oriented graph, consisting of a
transitive tournament joined from a set of isolated vertices....... 24
2.9 A Pmsaturated oriented graph......................................... 26
2.10 No oriented graph on 3 vertices is C^saturated...................... 28
2.11 The addition of either arc v\Vm or arc vmv\ generates a hamiltonian
cycle................................................................ 28
3.1 The 3sun in which the white vertices form an AT...................... 32
3.2 The bold edges form an asteriodal triple of edges..................... 34
IX
3.3 Three graphs, called insects, that contain an exobiclique.............. 34
3.4 An edge asteroid of order 5. Note that joining either vertex in e4
to any vertex on the path between the two white vertices, inclusive,
eliminates this property........................................ 35
3.5 An ATE that is not an EA of order 3.................................... 35
3.6 The addition of edge {Â£i+1, yi+k+i} creates an ATE..................... 40
3.7 Possible configurations of the vertices Oj, aj+i ...................... 41
3.8 a*, Oj+i in the same partite set....................................... 41
3.9 Possible configurations when Oj, ai+i in different partite sets .... 42
3.10 The forbidden subgraphs G\ and G3..................................... 43
3.11 The basic minimally noncircular arc graphs........................... 46
3.12 A graph and its circular arc representation........................... 47
4.1 The Coxeter graph...................................................... 51
4.2 A (l,3)tree and the associated graph in Tig........................... 51
4.3 S(C5) builders (subscripts indicate value of n (mod 7))................ 56
4.4 Exceptional /\4type Lobes ............................................ 59
4.5 The graphs E3, E'3, and E3 ............................................ 61
4.6 A graph G and the modifications G(e) and G(v, e) .................. 67
4.7 The graph J3 and a Ci2builder based on it ......................... 68
4.8 Every edge in a modified snark is on a long cycle.................... 71
4.9 An S(A'5)saturated graph of order 18. (d = 4, r 2)................ 79
4.10 Examples of AVsubdivisions in G(5,18) +uv. Open circles represent
the branch vertices of the subdivisions formed...................... 81
4.11 G(6, 21), an S(A'6)saturated graph of order 21. (d = 4, r = 1) ... 82
x
4.12 Examples of AVsubdivisions in G(6, 21) +uv. Open circles represent
the branch vertices of the subdivisions formed....................... 83
5.1 An edgecritical P3, P3 coloring of a graph........................ 86
5.2 The Petersen Graph KG(5, 2)........................................ 87
5.3 A colored subgraph of every edgecritical A3, K3 coloring of a graph 90
5.4 Minimal edgecritical P3, Ke coloring of P......................... 91
5.5 An edgecritical G, P3 coloring of a graph H in which n(G) =
7,5{G) = 3 .......................................................... 92
5.6 An edgecritical G, G coloring for k'(G) = 1....................... 93
5.7 G has a pair of adjacent degree 2 vertices not on a triangle....... 94
6.1 The addition of arc xy to s(A4 U Ah) does not create a Ah,(4,0) 98
xi
1. Introduction
1.1 Prologue
Graph Saturation is a subfield of Extremal Graph Theory, which itself has
its roots in Ramsey Theory [52] in 1930 and the work of Mantel [46] in 1907.
Brought to the forefront of Graph Theory by Turan [56] in 1954, Graph Sat
uration has been popularized and extended by a number of mathematicians
throughout the latter half of the twentieth century. Gfree graphs, that is
graphs not containing subgraphs isomorphic to some simple graph G, specif
ically edgemaximal Gfree graphs, have been studied in particular with respect
to maximizing and minimizing number of edges. In this chapter we give a brief
history of the study of Graph Saturation and introduce definitions and notation
that will prove useful throughout.
One mostly overlooked problem within Graph Saturation is the extension
of the field into oriented graphs. In Chapter 2 we attempt to address this
missing piece of the puzzle by demonstrating the existence of arcmaximal D
free graphs for all oriented graphs D, and determine the minimum number of
edges in specific cases.
Interval graphs were first introduced in 1957 with the work of Hajos [33].
Their applications are myriad, with current interest driven primarily by the
study of genomics. Eckhoff considered interval graphs in light of Extremal Graph
Theory in [19]. In Chapter 3 we change our focus from maximizing and mini
mizing the number of edges in saturated graphs and oriented graphs to continue
1
this work. We attempt to characterize all edgemaximal graphs meeting certain
properties related to interval graphs.
In Chapter 4 we return to minimizing the number of edges in certain sat
urated graphs. Topological minors, related to graph subdivisions, are useful in
determining planarity [42] and network design. We give upper bounds for the
number of edges in certain saturated graphs related to subdivisions, and provide
an asymptotic result.
An edgecoloring approach to Graph Saturation has also become an area
of interest with socalled Ramsey Turan Theory. Hanson and Toft [34] and
Grossman [31] have made inroads into this area. In Chapter 5 we look at a new
problem in this area and determine some results. In the final chapter we extend
some combinatorial games on graphs to oriented graphs.
1.2 Notation
We begin with some terminology and definitions, and refer to [58] as an
excellent resource.
A graph G = (V, E) is a nonempty finite set V(G) of vertices together with
a set E(G) of unordered pairs of distinct vertices of G called edges. For a graph
G with vertices u, v G V(G) the edge e = {u, v}, or sometimes uv, is said to join
u and v. For brevity we will sometimes use the notation v G G (e G G) instead
of v Â£ V(G) (e Â£ E(G)). We refer to u and v as being adjacent, and denote this
relationship by u ~ v. If u and v are not adjacent, this will be denoted u ^ v
and we will sometimes refer to a nonadjacency between the vertices. A graph
defined in this way, with at most one edge between any pair of vertices and no
vertex v with the property that v ~ v, is called a simple graph. Throughout we
2
primarily consider simple graphs and define any variation explicitly.
The order of a graph G is the cardinality of its vertex set, denoted either
I/(G) or n(G). The size of G is the cardinality of its edge set, denoted either
E(G)\ or e(G). and For a vertex v Â£ V(G), the degree of u, denoted da(v)
or simply d(v) where the context makes clear the graph G, is the number of
edges incident with v. The neighborhood of v, denoted Nq(v) or N(v), is the set
of vertices adjacent to v. The minimum degree and maximum degree of G are
denoted 5(G) and A(G), respectively. A graph in which 5(G) = r = A(G) for
some integer r is referred to as rregular.
A graph H is a subgraph of G if V(H) C V(G) and E(H) C E(G), and here
G is referred to as a supergraph of H. For simplicity this is denoted H C G. For
a graph G and a set S C V(G) we define the induced subgraph G[
graph with vertex set S and edge set T = {e : e Â£ E(G), e C S}. Note that by
these definitions not all subgraphs are induced subgraphs of G.
If G and H are graphs then their union is the graph G U H with vertex set
V(G) U V(H) and edge set E(G) U E(H). If v is a vertex not in G then by
G + v we will mean the graph G U {u}. The complement of G, denoted Gc, is
the unique graph with same same vertex set as G and an edge between vertices
u and v if an only if u v in G. If e Â£ Gc then G + e will denote the graph
with vertex set V(G) and edge set E(G) U {e}. Similarly, if v and e are in V(G)
and E(G) respectively then G v,G e denote, respectively, the graph G with
v and all incident edges removed and the graph G with edge e removed.
A graph G in which there exists a partition of V(G) into sets X and Y
where there is no edge among the vertices in X nor among the vertices in Y is
3
called bipartite, or simply a bigraph, with parts X and Y. We will denote this
by G = (X, Y). IfV(G) can be partitioned into k >2 such sets then G is called
k partite, and more generally multipartite.
Let G and H be graphs. G is isomorphic to H if there is a bijection 0
between their respective vertex sets that retains adjacencies and nonadjacencies,
which we will denote G = H. The join of G and H, denoted GV H, is the graph
with vertex set V(G) U V(H) and edge set consisting of all edges in E(G) and
E(H), as well as all edges of the form {u,v} where u G G,v G H.
A clique in a graph G is a subgraph H C G in which there is an edge between
every pair of vertices in H. If G is itself a clique then G is a complete graph
of order n(G), or G = Kn(c) An independent set in G is the complement of a
clique. A bipartite graph G = (X,Y) is complete if for every x G X,y G Y G
contains the edge {x,y}. If JA = s, T = t then the complete bipartite graph
with parts X and Y is denoted Kst.
If u and v are vertices of the graph G then a uv path, if it exists, is an ordered
set of distinct vertices uxix2... x^v in which {u,Xi},{xk,v},{xi,Xi+i}^ G
E(G). The length of this path is the number of edges traversed, i.e. one less
than the number of vertices, inclusive. We will use the notation for a path
of length k 1. If P = v\, v2,..., and P\ = v2,..., Vk\ then we will say that
P = V\PiVk The distance between u and v is the length of the shortest path
over all u v paths. A cycle is a path with the same starting and ending vertex.
Its length is defined to be the number of vertices. If a cycle C has length k then
it is sometimes referred to as a kcycle, and will be denoted Ck. G is connected if
for every pair of vertices u,v G G, G contains a u v path. If G is disconnected
4
then its maximal connected subgraphs are referred to as its components. A tree
is a connected graph containing no cycles. A forest is a graph in which all of its
components are trees.
Let G and H be graphs. H is Gfree if it does not contain a subgraph
isomorphic to G. H is maximally Gfree, or Gsaturated, if H is Gfree but
for any edge e G Hc the graph H + e contains a subgraph isomorphic to G.
For a fixed n, the saturation number sat(n, G) denotes the fewest edges in a
Gsaturated graph on n vertices, and the extremal number ex(n, G) denotes
the greatest. Finally, an edge e in G incident with the vertices it, v G G can
be subdivided by the removal of e, the addition of the vertex x and the edges
{x, u}, {x, v}. If an edge of G is subdivided then G is also said to be subdivided.
We now turn our attention to oriented graphs. An orientated graph D =
(V,A) consists of a set of vertices V(D) and a set of arcs A(D), consisting of
ordered pairs of vertices in V(D). For vertices u,v G D the arc (it, v) has initial
vertex u and terminal vertex v. If D is the oriented graph D = {V,A) and G
is the graph with V(G) = V(D) and E(G) = {{it, u} : (it, v) G A(D)} then G
is the underlying graph of D and D is an orientation of G. Subdigraphs and
superdigraphs are defined similarly to subgraphs and supergraphs. An oriented
graph is (r,r)regular if each vertex has precisely r outneighbors and r in
neighbors.
An ordered set of vertices ux 1X2 x^v in which (it, xi), (x*, x*+i fc1, (**,)
A(D) is a directed uv path. If u = v then this is a directed cycle. A tournament
T is an orientation of a complete graph. If there is a it v directed path for
every ordered pair of vertices it, 1? G T then T is strong. If there is a labeling of
5
the vertices of T of the form {t1; u2,..., vn} such that for every 1 < i < (n 1)
(vi,vi+1) G A(T) then T is the transitive tournament of order n.
1.3 Background
The first theorem addressing edgeextremal graphs with forbidden subgraphs
was the following result of Mantel and his students in 1907 [46].
Theorem 1.3.1. Let G be a simple graph on n vertices. If G has more than
LtJ e(^9es then G contains a subgraph isomorphic to K3.
Mantel proved that this result is best possible, thus ex(n, Kf) LxJ
Extremal Graph Theory continued with a theorem of Ramseys from the
field of philosophy. It was originally stated as follows [52]:
Theorem 1.3.2. Let T be an infinite class, and p and 7 positive integers; and
let all 7combinations of the members of T be divided in any manner into p
mutually exclusive classes Ci (i = 1, 2,..., p), so that every 7combination is a
member of one and only one Ci; then assuming the axiom of selections, T must
contain an infinite subclass A such that all the 7combinations of the members
of A belong to the same Ci.
Theorem 1.3.2 is often restated using only graph theoretic terminology:
Theorem 1.3.3. Let a, b > 1 be integers. There exists a smallest integer r =
R(a, b) such that every coloring of the edges of the graph I\r with the colors red
and blue contains either a red subgraph isomorphic to Ka or a blue subgraph
isomorphic to Kf.
6
Turan extended Theorem 1.3.1 to larger forbidden complete graphs in [56].
Note that it is often convenient and more elucidating to discuss graphs that
realize saturation numbers rather than the values themselves.
Definition 1.3.4. Let r,n be integers, 1 < r < n. Denote by Tr~1(n) the
unique complete (r 1)partite graph on n vertices the order of whose partition
sets differ by at most 1, and by tri(n) the number of edges in Tr^1(n). This
family comprises the Turan graphs.
Theorem 1.3.5. [56] Let G be a simple Krfree graph. Then, G has at most
tri(n) edges, and G is isomorphic to Tr~1(n).
Therefore, ex(n, Kr) = tr\(n). We refer to similar problems as Turantype
problems.
Erdos, Hajnal, and Moon [21] extended this idea in the other direction, and
determined the fewest number of edges in a ivrsaturated graph on n vertices,
and proved that their construction is unique, (Fig. 1.1).
Theorem 1.3.6. The smallest number of edges in a Krsaturated graph on n
vertices is (r1) + (r 2)(n r + 2). The only Krsaturated graph on n vertices
containing sat(n, Kr) edges is Kr_2 V /\_r+2.
Thus, the saturation number of Kr on n vertices is sat(n, Kr) = (r~:) + (r
2)(n r + 2).
We continue our generalization of complete graphs even further by consid
ering disjoint unions of cliques.
Let t be a positive integer and G a graph. By tG we mean t disjoint copies
of G. In [24] Faudree, Ferrara, Gould, and Jacobson determined precise values
7
Figure 1.1: The unique graph realizing sat(8, K6)
Figure 1.2: The unique smallest 3A3saturated graph on 12 vertices
for both sat(n, tKp) and sat(n, Kp U Kq).
Theorem 1.3.7. Let t,p,n be positive integers, p > 1. sat(n,tKp) is realized
by the graph Kp_2 V {(f l)Ap+i U I\n_pt_t+3}.
Though it is not yet known whether or not this graph uniquely realizes
sat(n,tKp) for all t, it does when t = 2 or t = 3, (Fig. 1.2).
Theorem 1.3.8. Let 1 < p < q, n be integers. sat{n, Kp U Kq) is realized by the
graph A'p_2 V {A'g+i U Kn_q_p+1}.
We now turn our attention to paths, trees, and forests.
Kaszonyi and Tuza [41] determined the saturation number for various acyclic
graphs.
8
Figure 1.3: The unique smallest A'i,ssaturated graph on 14 vertices
Theorem 1.3.9.
sat(n, =
(V) + rn */* < n <
3k3
r^n
1 */
3k3
< n
8 I V 2
The graphs that realize these values are A'fciUATfc+i and the disjoint union
of A'ljj with a (k l)regular graph on n _Â§J vertices (Fig. 1.3), respectively,
and are unique.
In [41], Kasonyi and Tuza show that for any nonstar tree T on k vertices,
sat(n,T) < sat(n, Ki'ki) This is especially evident in the case where T is a
star with a single subdivided edge. In fact, in [24] the authors show that, if To
is the subdivided star on k vertices and T is any tree isomorphic to neither T0
nor A'i,fci, then n j = sat(n,To) < sat(n,T) < sat(n, A'i,fc).
This brings us to a very curious property of the saturation function. It is
well known that for graphs G C H and an integer n, ex(n, G) < ex(n, H). It is
also clear that for families T C of graphs, ex(n,!R) < ex(n,T). The same is
not true for the saturation function.
To show the nonmonotonicity of sat in the former case, consider the graph
Gk = A'u._j + e, that is, a star with the addition of an edge between two
leaves. Pikhurko showed [51] that satin, Gk) = n 1 < sat(n, Ah,fci). In fact,
9
f t
/ \
Figure 1.4: A Pe saturated graph
it is KitTl_i itself that realizes this value. In the latter case, the authors of [23]
consider IF = {G&}, $ = {Gk, Ad,fci}. Again, it is clear that a star on n vertices
realizes sat(n, T) = n 1 and that sat(n,%) = sat(n, A'i^i), which we see in
Theorem 1.3.9 is larger than n 1.
Theorem 1.3.10.
Then, for n > asat(n, Pk) = n and is uniquely realized by a forest
with L^J components. Each component is a tree with depth at most [y] and
is 3regular except for the leaves and at most one vertex, of degree 4 or more,
which is adjacent to a leaf, (Fig. 1.4)
It is natural to consider the extreme case in which we are looking for a path
of order n on n vertices, i.e. a hamiltonian path. In [28] Frick and Singleton
determined sat(n, Pn) for large n.
Theorem 1.3.11. For n > 54 sat(n,Pn) = ^y^].
An mpath cover of a graph G is is a subgraph H consisting of at most m
disjoint paths with the property that V(H) V(G). In [22] Dudek, Katona,
Let ak =
3.2m_1 2ifk = 2m
4 2m~1 2 if k = 2m + 1
10
and Wojda generalized the result from Theorem 1.3.11 to mpath covers. We
can think of this as a sort of linear forest saturation.
Theorem 1.3.12. Let 1 < m < n be integers, and let mPCSn denote the family
of graphs on n vertices containing an mpath cover. Then, n 3m 3 <
sat(n, mPCSn) < n 2m + 2.
Now we consider (^saturated graphs. We will only examine the few exact
known results in this chapter. A more extensive list of results, including bounds
for a number of cases, can be found in the introduction to the fourth chapter of
this thesis.
Note that, since C3 = K$, the value for sat(n, C3) is determined by Theorem
1.3.6. In 1972, Ollmann [48] and later Tuza [57] determined the saturation
number for cycles of length 4, and determined all graphs realizing this value.
Theorem 1.3.13. Let n > 5. sat(n,Ci) = Iyy*].
In 1995 Fisher, Fraughnaugh, and Langley [26] found an upper bound for
sat(n,C5), but it was not until 2009 when Y.C. Chen [9] showed this to be a
lower bound as well, for sufficiently large n.
Theorem 1.3.14. sat(n, C5) < [y (n 1)]. This becomes equality for n > 21.
Other authors have examined saturated graphs in a variety of other con
texts. Hajnal [32] and DuffusHanson [18] considered the result of placing de
gree restrictions on clique saturated graphs. Hanson and Toft [34] related graph
saturation to edgecoloring, which we will look into further in chapter 5. Finally,
Bollobas [3] and Pikhurko [49], [50] studied saturated hypergraphs. See [23] by
11
J. Faudree, R. Faudree, and J. Schmitt for an excellent survey on the topic,
including a number of other results.
12
2. Oriented Graph Saturation
2.1 Introduction
Throughout this chapter we will refer to a simple graph as a graph. Let a(n
oriented) graph H contain G as a subgraph (subdigraph). We call the subgraph
of H that is isomorphic to G an embedding of G in H. Recall that for any
n > n(G) there is a Gsaturated graph H on n vertices, so both sat(n, G) and
ex(n, G) are welldefined. Let D, F be oriented graphs such that D is not a
subdigraph of F but the addition of any arc between nonadjacent vertices of F
results in a copy of D. We say that F is Dsaturated. If G is a graph and D is
an orientation of G then G = u(D), the underlying graph of D.
2.2 Motivation for extension to oriented graphs
While a number of results have been obtained regarding simple graph satu
ration, there has been very little work on oriented graph saturation. The little
that has been determined has been restricted to orientations of multigraphs [8],
[20].
Arcextremal oriented graphs with forbidden subdigraphs are a natural ex
tension of edgeextremal graphs with forbidden subgraphs. However determining
the existence of Dsaturated oriented graphs is not as trivial as in the undirected
case. To see this, we need only consider D containing a directed cycle. If F
is an acyclic oriented graph with nonadjacent vertices u,v then an arc can be
added between them, with the resulting superdigraph acyclic.
This led to a second problem. Given a simple graph G and integer n > n(G),
ex(n, G) has traditionally been defined to be the maximum number of edges in
13
Figure 2.1: G with edges xy and xz, G' with edge x'z' and nonedge x'y', and
G* with edge x*z* and nonedge x*y*
a Gfree simple graph on n vertices. Considering the transitive tournament
on n vertices, a strict extension of this definition to arcs in oriented simple
graphs would mean that ex(n, D) = () for any oriented graph with directed
cycles. This clearly does not reflect the spirit of the study of extremal graphs and
oriented graphs. In order to extend the definition to something more meaningful,
we denote by ex(n, D) the maximum number of arcs in a Dsaturated oriented
simple graph on n vertices.
2.3 Existence of saturated oriented graphs
Consider an undirected graph G. For x,y G V(G) we call a = xy Â£ E{G) a
nonedge. Define the surgery Ha,a in the following way:
Let G' and G* be two copies of the graph G xy, and for every vertex
v G V{G) label its associated vertices v' G G',v* G G*. Similarly, for every edge
a G E(G) {a} label the associated edges a' G G',a* G G*, (see Figure 2.1). If
14
Figure 2.2: The oriented graph Ho,a
D is an oriented graph with arc a then define HDa analogously.
Let Hc,a be the graph obtained by identifying x' with y* and x* with y'
(see Figure 2.2). We will show that the graph HG,a does not contain a subgraph
isomorphic to G via induction on the order of G.
Lemma 2.3.1. If v is a cut vertex of a graph G that is not an endpoint of the
edge a, F is a connected subgraph of Hq^, and neither v' nor v* are in F, then
there is another vertex w e G that is not an endpoint of the edge a such that
neither w' nor w* are in F and w is not a cut vertex of G.
Proof. Let A, B be components of G v such that a e A. The component B
contains at least one vertex w that is not a cut vertex of G. Every path from the
endpoints of the edge a to w in G contains v, so if the embedding of F contains
w' or w* then it must also contain either v' or v*. If neither v' nor v* are in the
embedding of F, then neither are w' nor w*, (see Figure 2.3).
Theorem 2.3.2. If G is a connected graph of order at least two, then for any
a E(G) there is no subgraph in Hg.o. isomorphic to G.
Proof We use induction on the order of the graph G. If G = K? then Ha,a
is a pair of isolated vertices. Since the resulting graph is edgeless, the theorem
15
Figure 2.3: Cut vertices v',v* and noncut vertices w',w* in HG,a ~ F
is true in the case of n(G) 2. Now assume that the claim is true for every
connected graph with order strictly less than k. That is, if F is a connected
graph with order strictly less than k then there is no edge / G E{F) such that
F C Hfj.
Let G be a connected graph of order k with at least one edge a = xy such
that G C Ha,a Note that e(G {a}) = e(G) 1, and e(HG,a) 2e(G) 2.
Hence it follows that there must be an edge a G E(G a) such that both a'
and a* are in this embedding of G. If no such edge exists then every edge in
e(G) {a} appears at most once in the embedding and e(G) < e(G) 1, which
is impossible. We now show that there is a vertex w G G {x, y} such that
neither w' now w* is in the embedding of G.
Case 1: Say that a = V1V2 with V\,V2 Â£ {x,?/}. Since both a' and a* are in
this embedding of G, it follows that v[,v'2,vl,V2 are as well. The embedding of
G contains n(G) 4 other vertices, so at most n(G) 2 remaining vertices of G
appear at least once in this embedding. So, there are at least twro vertices in G
w,z G V(G) such that none of {w\ z', w*, z*} are in this embedding of G. Since
16
G is connected and (x', y'} = {x*, y*} is a cut set of Ha,ai at least one of {x', y'}
must be in this embedding of G. So, at least one of {10,2}, say w, is neither x
nor y. So there is a vertex w e V(G) {x,y} such that neither w1 nor w* is in
the embedding of G.
Case 2: Assume, without loss of generality, that V\X. Since both a' and a*
are in the embedding of G, the embedding of G includes both x' and x* = y'.
Since both v2 and v2 are in the embedding of G then by an argument analogous
to the one in the previous case there is a vertex w G V(G) such that neither w'
nor w* are in the embedding of G. The vertex w is neither x nor y since both
x and y are in the embedding of G.
Note that the edge a cannot be incident to both x and y in G {a} since
xy = a is a single edge in G.
So, in both cases there exists a vertex w e V(G) {x, y} such that neither
w' nor w* is in the embedding of G. By Lemma (2.3.1) we can assume that w is
not a cut vertex of G. So, G w is connected and contains the edge a, and the
embedding of G is also contained in HcW,a The graph G w C G C HcW,a
and n(G w) < k, which contradicts our inductive assumption. Therefore, for
any connected graph G and single edge a 6 E(G) there is no subgraph of Ha,a
isomorphic to G.
Let D be an oriented graph. We want to show that there is some integer
Nd such that for every n > Np there is an oriented graph F on n vertices that
is Dsaturated.
Lemma 2.3.3. If there is an oriented graph H on n vertices with nonadjacent
vertices x and y without a subgraph isomorphic to D, but D is a subgraph of both
17
H + xy and H + yx, then every tournament containing H also contains D. So,
there is an oriented supergraph of H on the vertices of H that is Dsaturated.
Theorem 2.3.4. For every oriented graph D there is some integer No such that
for every n > No there is a graph H on n vertices with nonadjacent vertices
x,y Â£ V(H) not containing a subdigraph isomorphic to D but with the property
that both H + xy and H + yx contain subgraphs isomorphic to D.
Proof First consider the case where u{D) is connected. Let Np = 2n(D) 2,
say a Â£ A(D), and let Hp a be the surgery as defined above. For n > 2n(D) 2,
define H to be the graph Hd^ U KnND, (see Figure 2.4). By Theorem 2.3.2,
u(D) is not a subgraph of u(Hda), and hence D is not a subdigraph of H.
However, the addition of either the arc xy or the arc yx creates a copy of D. By
Lemma 2.3.3, there is a .Dsaturated oriented graph on n vertices.
If u(D) is not connected then let J be the component of D with greatest
order. Let a be an arc in J and let H = HJ>a U (D J). Since Hja does not
contain a copy of J, H does not contain a copy of D.
Therefore, given any oriented graph D and integer n > 2n(D)2 sat(n, D), ex(n, D)
are welldefined.
2.4 Results
For each m define Pm to be the directed path on m vertices.
Theorem 2.4.1. sat(n, P3) = n 1
Proof. The lower bound is achieved by orienting all edges of A'i,ni into the
center vertex, (see Figure 2.5). If any oriented graph D contains fewer arcs,
18
Figure 2.4: The union of Ha,a with isolated vertices
Figure 2.5: The smallest /^saturated oriented graph on 7 vertices
then it is not weakly connected and must contain at least 2 oriented trees 7\
and T2. Every oriented tree contains both a source and a sink, which can be
easily seen by considering the endpoints of any maximal directed path. If neither
tree contains a then neither does the graph with an added arc from a source
of Ti to a sink of T2.
Theorem 2.4.2. 1.
sat(n, P4)
n i/3n
n 1 otherwise
19
Figure 2.6: A P5saturated oriented graph
2.
/
sat(n, P5) <
n
< n + 2
n + 4
*/3 n
if n 1
if n = 2
mod 3
mod 3
3.
sat(n, PÂ§) <
n if 3n
n + 2 ifn= 1 mod 3
n + h if n 2 mod 3
Proof To see the upper bounds, consider the oriented graph composed
joint directed 3cycles and possibly the following, depending on parity:
of dis
1. An isolated vertex or P2 for sat(n, P4)
2. One or two strongly oriented AT4s for sat(n,P5), (see Figure 2.6)
3. A strongly oriented Ah or K5 for sat(n, P6).
For the sharpness of sat(n, P4) we consider two cases. If 3 \ n and D is a
P4free oriented graph on n vertices with fewer than n 1 arcs, then D has at
least 2 components that are oriented trees. Each contains a source and a sink,
and any added arc from the source of one to the sink of another will not create
a P4. Consequently if 3n and D has fewer than n arcs, then there is at least
20
one component T that is an oriented tree, and T must contain a source and a
sink. If all sinks are out neighbors of all sources, then the component is an in
or outstar which itself is not P4 saturated. If there is a source not adjacent to
a sink then this added arc does not result in a P4. So, we have sharpness.
We now determine the exact value for the saturation number of an oriented
star.
Theorem 2.4.3. Let Ah,(aj&) be the directed star with indegree b and outdegree
a. If a ^ b and k = max{a, b} then sat(n, = n(k 1)
Proof. Refer to the directed star Ki^aib) as K. Say D is an oriented graph on
n vertices that is A'saturated. For any pair u,v of nonadjacent vertices we
require that DUuv and DUvu both contain a copy of K. So, either d~(u) > b
and d+(u) = a 1, or d+(v) > a and d~(v) = b 1, and either d~(v) > b and
d+{v) = a 1, or d+(u) > a and d~{u) = b 1. If d~{u) > b and d+(u) > a, or if
d+(v) > a and d~(v) > b, then D contains K and so D is not A'saturated. The
only 2 of the 4 possible combinations that dont result in D already containing
K are when either both u and v are centers of a Ki^a b) or both are centers of
a We refer to this property as u and v being of the same type Without
loss of generality we can assume that a > b. So, any vertex v is either adjacent
to or from every other vertex, d+(v) = a 1, or a < d+{v) < n 1. Since
the sum of all outdegrees is equal to the sum of all indegrees, D contains at
least In[(a 1) 4 (a 1)] = n(a 1) arcs. This bound is realized by a regular
oriented graph on n vertices with degrees (a l,a 1), in which the former
represents the outdegree of each vertex and the latter represents the indegree
21
of each vertex, which is Dsaturated.
Note that Theorem 2.4.3 only holds for orientation in which the outdegree
of the center vertex differs from its indegree. If they are the same then we get
a different result.
Theorem 2.4.4. sat(n, Ki,(a,a)) = (n l)(a + 1)
Proof. Consider a (a 1, a l)regular oriented graph D on n1 vertices, joined
from a single vertex v, (see Figure 2.7). Every vertex other than v has degree
(a, a 1), and any new arc must be from one of these to another. So, D is
Ad,(a,a)saturated. Now let F be a A^^^saturated oriented graph. Notice, as
in Theorem 2.4.3, that every vertex in F with a nonneighbor is at the center
of a Ffi,(a,ai) or a Ab,(ai,a)> with nonadjacent vertices of the same type. Note
that every vertex must either be at the center of a A'it(a_ii0_i) or share an arc
with every other vertex. If every vertex has a nonadjacency, then, in order to
preserve equality of in and outdegree sums in F, we must have at least one
arc xy or yx such that x is at the center of a K\,(ai,a) and y is at the center of
a A'ii((1)a_i). Therefore x shares an arc with every vertex of the same type as y
and y shares an arc with every vertex of the same type as x. The number of arcs
added in this manner is minimized when the xtype or ytype sets of vertices is
of order 1. However, this yields a graph of the same size as our construction,
and hence weve minimized F.
We conclude this section with another definition and a familiar construction.
22
Figure 2.7: A Ad,(3,3)saturated oriented graph
Definition 2.4.5. Let G,H be graphs and let kG{H) denote the number of
subgraphs of H isomorphic to G. H is strongly Gsaturated if for any edge
e e Hc kG{H + e) > kG(H).
Note that any Gsaturated graph is strongly Gsaturated, but the converse
is not necessarily true.
Theorem 2.4.6. IfTTm is the transitive tournament on m vertices then
(m 2\
sat(n, TTm) = ( j + (n m + 2)(m 2).
Proof Erdos, Hajnal, and Moon [21] showed that sat(n, Km) = (mf2) + (n
m + 2)(m 2) by considering Km2 V A'n_m+2 Orient the (m 2)clique to
obtain 7Tm_2 and each arc from the remaining vertices to this tournament, (see
Figure 2.8). The resulting oriented graph F is TTmsaturated and provides an
upper bound on sat(n,TTm). Now let J be a TTmsaturated oriented graph
with x,y J nonadjacent vertices. Since J + xy, J + yx both contain TTm, the
23
Figure 2.8: A transitive tournament saturated oriented graph, consisting of a
transitive tournament joined from a set of isolated vertices
addition of xy to u(J) creates a new copy of Km. Therefore, u(J) is strongly
A"msaturated. In [2] it is shown that A'm_2 V AAm+2 is the unique smallest
strongly A'msaturated graph on n vertices. Therefore u(.J) is A'm_2 V Knm+2
and J has (m~2) + (n m + 2)(m 2) arcs. Therefore,
2.5 Some Upper Bounds
We begin our examination of bounds on sat with a definition followed by
an examination of path orientations.
Definition 2.5.1. An oriented graph D is hamiltonian connected if for any
pair x,y of vertices of D there is a hamiltonian path from x to y and from y to
x.
24
Let k > 7 be an integer. We will now construct a hamiltonian connected
tournament of order k. Define the digraph Dk with vertices v0, V\,..., vk~\ and
arcs ViVi+\,ViVi+i, and ViV\+3 for all 0 < i < (k 1) with addition modulo k.
Lemma 2.5.2. The digraph Dk is hamiltonian connected.
Proof. We require that for every ordered pair of vertices in Dk there is a hamil
tonian path from the first to the second. Without loss of generality we may
assume that the ordered pair is of the form (u0,Uj) for some 1 < i < (k 1). If
1 = (k 1) then the path vqV\ vk1 is hamiltonian. If i < (k 1) is odd then
consider the path v0v2V4 ... vi+iVi+2 ... vk\V\V3 ... Vj. If on the other hand i is
even then the path VqViV^ ... Vi+\Vi+2 ... vk\V2Vi ... Vi will suffice. Therefore,
there is a hamiltonian path from vq to every other vertex in Dk, and thus Dk is
hamiltonian connected.
Because Dk is a hamiltonian connected digraph of order k > 7, so is every
tournament of order k that contains Dk as a subdigraph. Therefore Lemma
2.5.2 implies the existence of hamiltonian connected tournaments of all orders
at least 7.
Theorem 2.5.3. Let n > m > 9 be integers. Then, n < sat(n, Pm) < (mf2) +
2 (n m + 2).
Proof. First, note that the argument in the proof of Thm. 2.4.1 applies here as
well, so that no Pmsaturated oriented graph contains a pair of oriented trees. In
fact, a single oriented tree is either P3saturated, and therefore not Pmsaturated,
or contains both a source and sink. Joining the source to the sink does not create
a Pm. Therefore n < sat(n, Pm).
25
c:
Figure 2.9: A Pmsaturated oriented graph
For the upper bound consider the following oriented graph H(m,n), seen
in Figure 2.9. Let Pm_2 be a hamiltonian connected tournament on m 2
vertices whose existence is guaranteed by Lemma 2.5.2, with vertices labelled
um_3. Add n m + 1 vertices labelled ro, rl5... rn_m and adjacent
from Vq. Finally, add a new vertex u adjacent to vq, tq, ... rn_m. The graph
H(m,n) is Pmsaturated. This can be seen by first noticing that the longest
path in H(m, n) has order m 1, then examining the graph H(m, n) + a for any
arc a G H(m, n)c. Let i,j be integers. If a = r^rj then the path um_3 ... Vor^j
is a Pm. If a = v{rj then consider the path tWoP^t^r^ where Pqi is a hamiltonian
path from vq to Vi in Tm_2. Alternately, if a riVj then consider rjUj.P,oA)> unless
i = 0 in which case the path riVjPjori is a Pm. If a = ViU then let P be the path
of order m 3 obtained from Poj by removing the vertex u0. Then PviUv0ro is a
path of order m. Finally, if a = uvi then the path uViPioV0r0 suffices. Therefore,
H(m, n) is PTOsaturated and n < sat(n, Pm) < (m^2) + 2(n m + 2).
Note that if m is 7 or 8 then sat(n, Pm) is bounded above by n + c where c is
a constant depending on n (mod m). This bound is achieved by a construction
similar to that in Thm. 2.4.2 but composed of disjoint strong tournaments of
26
order 4 along with zero, one, two, or three strong tournaments of order 5 and,
in the former case, at most one directed 3cycle.
Theorem 2.5.4. Let o(Pm) be an orientation of Pm, with m = 2k, k > 8 and
odd. Then, sat(n, o(Pm)) < (n (mod k))(k+ LfJ^)
Proof. Consider the oriented graph F consisting of disjoint rotational tourna
ments of order k. Havet and Thomasse [36] showed that every tournament on
at legist 8 vertices contains every orientation of a hamiltonian path. So, each
vertex of F is an end vertex of every orientation of every path of order at most
the order of the component in which the vertex is contained. Thus, the addition
of an arc between vertices of different components will yield every orientation
of a path of order m. A similar result can be determined for m odd.
2.6 The minimum order of a Dsaturated oriented graph
We mentioned in Section 2.1 that for a simple graph G, sat(n,G) is well
defined for any n > n(G), and in Section 2.2 that this is not necessarily the
case for oriented graphs. Consider the case when D is a directed cycle on three
vertices, denoted C3. There are, up to isomorphism, only three oriented graphs
of order three and size two, (see Figure 2.10). For each, there is an arc whose
addition creates no C3. Consequently, sat(3, Cf) is undefined. However, the
directed cycle on four vertices is CVsaturated.
This leads naturally to wonder for which n sat(n, D) is defined. Given a
oriented graph D we refer to the smallest n such that sat{n, D) is defined as
Nd. Our surgery in section 2 of this paper gives 2n(D) 2 as an upper bound
on Nd
27
> M
 
Figure 2.10: No oriented graph on 3 vertices is C3saturated
Figure 2.11: The addition of either arc v\vm or arc vmv\ generates a hamilto
nian cycle
For the transitive tournament TTn on n vertices, the construction used in
Theorem 2.4.6 demonstrates that Ntt = n
Every vertex in a strong tournament on k vertices is both the initial and
terminal vertex of directed paths of order k. Therefore for m > 4 the oriented
graph on m vertices composed of an isolated vertex and a strong tournament on
m 1 vertices is Pmsaturated. A pair of isolated vertices is P2saturated, and
three vertices with a pair of arcs that share an initial vertex is a P3saturated
graph. So, Np = m for all m > 2.
Similarly, for m > 3 we can show that Nc~m = m. Consider a directed path
V\,V2, .vm on m vertices. Add the arcs and umu2, (see Figure 2.11).
The resulting graph does not contain a directed mcycle, but the addition of
either V\Vm or vmvi creates one, so by Lemma (2.3.3) there is a Cmsaturated
28
oriented graph on m vertices.
2.7 Future directions
I am also interested in applications to games on graphs and oriented graphs.
Ferrara, Harris, and Jacobson [25] determined the winner of fFsaturator, an
impartial combinatorial game involving the avoidance of certain simple graphs.
I would like to investigate similar games involving avoidance of certain oriented
graphs.
29
3. Maximal NonInterval Graphs and Bigraphs
This chapter represents joint work with B. Tonnsen.
3.1 Introduction
Definition 3.1.1. Let Â§ be a family of open intervals on the real line, and G
a graph defined by the elements of S in the following way. For each interval
s G S let vs be a vertex of G and join vertices vs,vt in G if and only if the
intervals s,t 6 S have a nonempty intersection. We say that S is an interval
representation of the graph G. Every graph for which an interval representation
exists is called an interval graph.
Definition 3.1.2. A bipartite graph G = (X,Y) is an interval bigraph if every
vertex can be associated with an open interval on the real line in which two
vertices x E X,y E Y are adjacent in G if and only if their associated intervals
have a nonempty intersection.
Note that we retain the bipartite property by not joining x\,x2 E X or
2/i, 2/2 E y even if their associated intervals intersect.
Interval graphs, and related families including interval bigraphs, proper in
terval graphs, and circular arc graphs, have been studied extensively, ([5], [6],
[7], [35], [38], [43], and [47]). We are primarily concerned with properties of these
families related to edgemaximality, which has thus far received little attention.
In [19] Eckhoff examines rextremal interval graphs, those interval graphs with
the maximum number of edges among those with fixed order and clique number
30
r, and characterizes them. We extend the study of extremal interval graphs
to those graphs that are not interval graphs and have the maximum number
of edges, and additionally we examine related families. Although there is a
known, simple forbidden subgraph characterization for interval graphs, and an
as yet incomplete and very different forbidden subgraph characterization for in
terval bigraphs, we show that the family of extremal noninterval graphs and a
subfamily of extremal noninterval bigraphs are very similar.
We will use 7 to represent both a graph property and the complete family
of all graphs with property 7.
Definition 3.1.3. Let 7 be a graph property and let G = (X,Y) be a bipartite
graph not in 7 such that any edge e = xy 6 Gc with x 6 X,y e Y the graph
G + e is in 7. We say that G is CPbisaturated.
In section 2 we characterize all CPjsaturated graphs for 7t the family of
interval graphs. We then characterize all dVbisaturated graphs, up to a con
jectured forbidden subgraph characterization, where 7b is the family of interval
bigraphs in section 3. In section 4 we address the family of edge maximal split
noninterval graphs. We end by examining unit interval and circular arc graphs.
3.2 EdgeMaximal NonInterval Graphs
Let G be a graph. An asteroidal triple in G is a set A of three vertices such
that between any two vertices in A there is a path within G from one to the
other that avoids all neighbors of the third. An example is in the 3sun in Fig.
3.1. Lekkerkerker and Boland showed that all interval graphs are completely
characterized by the absence of both asteroidal triples and induced cycles of
length greater than 3 in [43].
31
Figure 3.1: The 3sun in which the white vertices form an AT
Lemma 3.2.1. Any graph containing an asteroidal triple contains an induced
Pa
Proof. Let A = {x, y, z} C G be an asteroidal triple and assume that G does
not contain an induced P4. Between any two vertices in A, say x, y there is
a shortest path P(x, y) in G avoiding the neighbors of the 2. P(x, y) cannot
have length 1 since there is a z, y path that avoids all neighbors of x and thus
y cannot be a neighbor of x. If P(x, y) has length 3 or greater then it contains
an induced P4. Therefore P(x, y), P(x, z), P(y, z) all have length 2. These three
paths are internally disjoint so G contains a 6cycle xaybzca. If {a, b, c] are
not mutually adjacent then G contains an induced P4. Thus G contains the
3sun as a subgraph. If {a, b, c, x, y, zj does not induce the 3sun then one of
the asteroidal paths P(u, v) between two vertices in A contains a neighbor of
the third. However, the 3sun, and thus G, contains the induced P4 yacz.
Let CP* denote the set of interval graphs.
Theorem 3.2.2. Saf(n,lPj) = {C4 V Kn4},n > 4
32
Proof. Say G Â£ Sat(n, T*). By Lemma 3.2.1 G cannot contain an asteroidal
triple since the endpoints of an induced P4 can be joined to create an induced
C4, which is another of our forbidden subgraphs. Therefore, G must contain an
induced cycle of length at least 4. If G contains an induced Ck, k > 4 then there
is a pair of vertices that when joined create an induced C4. So, G must contain
an induced 4cycle C. If there is an edge e Â£ Gc Cc then G + e still contains
the induced 4cycle, and thus is not an interval graph. Therefore, G must be a
4cycle joined to a complete graph.
Note that the family of maximally noninterval graphs is the collection of
cliques with an isolated pair of edges removed, precisely the same as the family of
maximally nonchordal graphs. While there are noninterval chordal graphs con
taining asteroidal triples, we have shown that no such graph is edgemaximally
noninterval.
3.3 EdgeMaximal NonInterval Bigraphs
Throughout this section we are concerned with bipartite graphs G = (X, Y).
We sometimes choose to discuss part X or Y, but since there is no distinction be
tween parts X and Y this choice is merely made for convenience, and generality
should be assumed.
We begin by introducing some new structures.
Definition 3.3.1. [47] A set A = {a, c, e} of three edges of a graph G form an
asteriodal triple of edges (ATE) if for any two, say a, c, there is a path from one
endpoint of a to an endpoint of c that avoids all neighbors of the endpoints of e,
(see Fig. 3.2).
33
.1.
*N S
Figure 3.2: The bold edges form an asteriodal triple of edges
Figure 3.3: Three graphs, called insects, that contain an exobiclique
Definition 3.3.2. [38] Two sets A, B are incomparable if A <Â£. B and B
A. An exobiclique is a bipartite graph H = (X,Y) containing a biclique with
nonempty parts M C X and N C Y such that each of X XI and Y N contain
three vertices with incomparable neighborhoods in the biclique, (see Fig. 3.3).
Definition 3.3.3. [38] An edgeasteroid of order 2k + 1 is a set of edges
eo, e\,..., e2k such that, for each % = 0,1,..., 2k, there is a path containing both
e* and ej+i that avoids the neighbors of ei+k+1; the subscript addition is modulo
2k + 1, (see Fig. 34).
Note that the cycle CÂ§ contains an asteroidal triple of edges but is not
an edgeasteroid of order 3, since for any 3 pairwise nonincident edges any
pair have an endpoint in the neighborhood of the third, (see Fig. 3.5). Thus,
34
Figure 3.4: An edge asteroid of order 5. Note that joining either vertex in e\
to any vertex on the path between the two white vertices, inclusive, eliminates
this property.
although their definitions are similar, an edgeasteroid is not simply a generalized
asteroidal triple.
None of the structures in Definitions 3.3.1, 3.3.2, 3.3.3 are permitted as
induced subgraphs in an interval bigraph, as seen by the following theorems of
Muller, Hell and Huang, and Harary et al.
Theorem 3.3.4. A bipartite graph containing an induced asteroidal triple of
edges or an induced cycle with length greater than 4 is not an interval bigraph.
Theorem 3.3.5. A bipartite graph containing an induced exobiclique or an edge
asteroid is not an interval bigraph. [38]
Let 1P6 be the family of interval bigraphs.
Figure 3.5: An ATE that is not an EA of order 3
lS5j
35
There is currently no forbidden subgraph characterization of interval bi
graphs. However, the preceding theorems provide the most extensive known
collection of forbidden subgraphs. Though there are currently proposed bipar
tite graphs [37] that are not interval but do not fall into one of the cases addressed
in Theorems 3.3.4 and 3.3.5 the authors are not aware of any examples without
induced paths of length at least 5. Since joining the endpoints of an induced P5
creates an induced Cq no graph containing an induced P5 is UVsaturated.
We will return to this issue at the end of this section.
Definition 3.3.6. Let G = (A,B),H = (C,D) be bipartite graphs. The
bipartite joins of G and H are the graphs consisting of a copy of G, a copy
of H, and either all adjacencies between A and C and between B and D, or all
adjacencies between A and D and between B and C. Denote by G*H the family
of bipartite joins of G and H.
Lemma 3.3.7. Let G = (X, Y) be a Tbbisaturated bipartite graph of order n.
If G contains an induced Cq then there is an integer m < n such that G is a
graph in C6 Km,nm6
Proof. Assume not, and let C be an induced CÂ§ in G. There is a nonadjacent
pair of vertices x E X,y E Y such that without loss of generality x Â£ C. The
addition of edge xy to G creates an induced Cq and hence G is not an interval
bigraph. So, G must be of the form described.
Lemma 3.3.8. No Tbbisaturated bipartite graph contains an induced Pq.
Proof. Let G be a bipartite graph with v\, V2, vq an induced PÂ§. The addition
36
of edge vxv% creates an induced C6 in the new graph, and hence G is not 3V
bisaturated.
Lemma 3.3.9. Every asteroidal triple of edges contains either an induced P6
or an induced Cq.
Proof. Let G = lUhbea bigraph with an asteroidal triple of edges, a 0102,
b = bib?, and c = C1C2 such that ax,bi,cx G X and a2,b2,c2 G Y. Assume
there is no induced P$ or Cq in G, so a, b, and c cannot be alternating edges of
a Cq. Therefore, we assume there exists at least one minimal asteroidal triple
path, P1, with length at least 2. Without loss of generality assume this path is
between edges a and b. If Pl has 3 or more edges then it comprises an induced
P6 with edges a and b, so assume this path between a and b has length 2, and
label the vertices ax,d, bi. There exists a minimal path from edge b to c that
avoids the neighborhood of a, call it P2. Again if P2 has 3 or more edges then G
contains an induced Pa, so p2 has 1 or 2 edges. If P2 has length 1 and the path is
bxc2, then the edge Cia2 either exists, creating an induced Ce with a2axdbxcxcxa2,
or does not, in which case the vertices form an induced P6. Now assume the
edge comprising P2 is b2cx. In this situation, there are no more edges among
these 6, and a2axdbxb2cx is an induced P6. Therefore, let us assume that P2
has length 2. If P2 = 6ieci then, since there are no more edges among these
6 vertices, aid^ec^ is an induced Pq. So assume the path is b2ec2. The only
edges that would not eliminate the property that G contains an asteroidal triple
of edges are ed and a2Ci. If ed, a2cx G E(G), then c1a2aidec2Ci is an induced Cq.
Otherwise, if neither edge is in G then a2axdbxb2e is an induced P6. Finally, if
ed G E(G), but a2Ci ^ E(G), then a2axdec2cx is an induced Pe. If a2Ci G E(G),
37
but ed (Â£l E(G), then the 6 vertices create an induced C$, which contains an
induced P$. Therefore, G has an induced P6 or Cq.
By Lemmas 3.3.8 and 3.3.9 no bipartite graph with an asteroidal triple of
edges is UVbisaturated unless it is of the form CÂ§ Ki m for integers l,m.
Lemma 3.3.10. Every exobiclique contains either an induced P6 or an induced
C6.
Proof. Let G = (A, B) be an exobiclique with the property that for any edge
e G Gc, G + e is not an exobiclique. There are sets A', N C A and Y, M C B
such that H = (M, N) is a biclique and A, Y are sets of size at least 3 with
incomparable neighborhoods. There exist xi,x2 G A with neighbors mi,m2 G
M, respectively, such that xx m2 and x2 ^ mj. Similarly there exist yi, y2 G Y
with neighbors ni,n2 G N, respectively, such that yx ^ n2 and y2 nx. If xxy2
or x2y2 is an edge in G, then m\nim2x2y2ximi is an induced C$. Otherwise,
one of these edges can be added without eliminating the property that G is an
exobiclique, and thus G remains a noninterval bigraph.
By Lemmas 3.3.8 and 3.3.10 no bipartite graph containing an exobiclique is
OVbisaturated unless it is of the form Cq Kim for integers l, m.
Now consider G (X,Y), a bipartite graph containing an edge asteroid
{eo, ex,..., e2fc} of order 2k + 1. For each i e* is the edge joining Xj G A, G Y.
If the distance between the sets {xj,^} and {xj,yj} is greater than 2 for some
0
in which the distance between any pair of edges in an edge asteroid is at most
38
2. Note that for all 0 < % < 2k we have that no endpoints of either e* or ei+i is
a neighbor of either endpoint of ei+k+i.
Lemma 3.3.11. If h 1 then G contains an induced P6.
Proof. Let {xoyo,Xiyi,x2y2} be an edge asteroid of order 3 in G and assume
that G contains no induced Pq. The endpoints x% and y} are not adjacent for
any distinct pair i,j Â£ {0,1,2}, so without loss of generality there is a path
yoayi in G for some vertex a that is not the endpoint of an edge in the EA.
Similarly there is a distinct vertex b that is not an endpoint of an edge in the
EA such that either yiby2 or x\bx2 is a path in G. Therefore, x0yoayiby2 or
xoyoayiXib is an induced Pq in G.
Now assume that k > 1. First, consider the case in which there is some %
such that yt ~ xi+k+2.
Lemma 3.3.12. If yi+k+i ~ Xi+k+2 and Xi ~ yi+\ then G is not P\)bisaturated.
Proof. Let = yiXi+k+2, e2 = yi+1xi+k+1, e3 = yi+k+1xi+k+2. Note that eu e3 are
edges in G and e2 is not, (Fig. 3.6). The addition of e2, however, results in the
asteroidal triple of edges {ei,C2,e3}. By Lemma 3.3.9 G is not OVbisaturated.
Lemma 3.3.13. If yi+k+i ^ xi+k+2 or Xj 9^ yi+1 then G is not tPbbisaturated.
Proof. In the former case let e = xi+iyi+k+i, and in the latter let e = yi+iXi+k+\.
Let 6i = yiXi+k+i,e2 = ej+i,e3 = ei+k+i. The addition of edge e results in the
asteroidal triple of edges {ei,e2,e3}. By Lemma 3.3.9, G is not dVbisaturated.
39
Figure 3.6: The addition of edge {xj+i, yi+k+i) creates an ATE
Now, consider the alternate case in which there is no i such that yt ~ Xi+k+1
Lemma 3.3.14. Let G = (X,Y) contain an edge asteroid {e0, ei,..., e2fc} of
order greater than three with the property that for all i, yi oo xi+fc+2 and Xj
yi+k+2 Then, G is not Tbbisaturated.
Proof
Case 1: Assume that there is an i such that a shortest path between e* and ei+k+ i
includes the vertex a*, a shortest path between ej+i and ej+fc+2 includes
the vertex ai+i ^ aj, ej is not adjacent to aj+i, and e^+i is not adjacent to
a,. Then, we have one of the graphs in Fig. 3.7 as a subgraph of G. There
is a path from the endpoints of e* to the endpoints of ej+i that avoids the
neighbors of the endpoints of ei+k+\, and thus both graphs in the figure
contain an induced P6 that includes as a subpath yiaiyi+k+iXi+k+\. By
Lemma 3.3.8 G is not OVbisaturated.
Case 2: Now say that for all i there is a vertex a* such that e*, ej+i, ei+k+i ~ aj, as
depicted in Figure 3.8.
40
Figure 3.7: Possible configurations of the vertices ai,ai+1
Figure 3.8: at,ai+1 in the same partite set
Case 2a: There is an integer i such that a* and Oj+i are distinct vertices, (Fig.
3.9). If <2j,aj+i are in the same partite set of G, set X, then let
e = XiUi+k+2 The addition of e to G results in the asteroidal triple
of edges {ej, ej+j, 6j+fc+2}
If cii G X,ai+i G F, (Fig. 3.9), then either a* aj+i, in which
case ai?/i+ixi+iai+iXi+fc+2?/i+fc+2 forms an induced P6, or a* ~ ai+i, in
which case the addition of the edge Xiyi+k+2 completes an asteroidal
triple of edges among {e*, ei+k+2, ajai+1.
Case 2b: There is a vertex a in G that satisfies a* = a for all 0 < < 2fc. Let A
41
^3i+i
i+k+2
Figure 3.9: Possible configurations when di,ai+1 in different partite sets
be the collection of all such vertices, i.e. A = {a V(G) : a ~ efji}.
G' = G A has the same edge asteroid as G since no edge asteroid
path includes a vertex in A, and G' contains no vertex adjacent to all
edges of the edge asteroid. So, G' falls into Case 1 or Case 2a above,
and is an induced subgraph of G.
Lemmas 3.3.7 through 3.3.14 lead us to the following conjecture.
Conjecture 3.3.15. G is Pbbisaturated if and only if G E C& Ki m for some
integers l,m.
Note that this family of maximally noninterval bigraphs is precisely the
family of bicliques with 3 isolated edges removed.
Thus far we have assumed the forbidden subgraph characterization implied
by Theorems 3.3.4 and 3.3.5. While there are current attempts at constructing
examples of graphs that potentially invalidate this characterization, they are all
quite large. Because complete bipartite graphs are interval bigraphs any non
interval bigraph that avoids the aforementioned forbidden subgraphs contains a
42
Figure 3.10: The forbidden subgraphs G\ and Gz
high number of nonadjacencies. Therefore, we expect that any bipartite graphs
that violate the characterization will contain rather long induced paths. We
have examined one such graph, briefly mentioned at the top of page 323 in [38],
and supplied to us [37] by the authors of [38], and we have found it to contain
an induced Pj.
3.4 EdgeMaximal Split NonInterval Graphs
Definition 3.4.1. A graph G is a split graph if the vertices can be partitioned
into sets A and B such that the induced subgraph on A is a complete graph and
the the induced subgraph on B an independent set.
See Fig. 3.10 for examples in which the white vertices represent independent
sets and the black vertices cliques.
Let CPS denote the property of being an interval graph or a nonsplit graph.
Let Gi and Gz be the graphs in Fig. 3.10, and let G2 denote the 3sun in Fig.
3.1.
Foldes and Hammer showed [27] that a split graph is interval if and only
if it does not contain an induced subgraph isomorphic to one of the graphs
Gi, G2, Gz
43
Lemma 3.4.2. Gi,G2
Proof. G\ and G2 are both split graphs that contain asteroidal triples denoted
by {x,y,z} in Figure 3.1 and the white vertices in Figure 3.10. Any edge that
can be added to either graph without resulting in an interval graph is an edge
that eliminates the split property. However, the addition of edge ab to G3,
(see Fig. 3.10), does not destroy the asteroidal triple nor result in a nonsplit
graph.
Theorem 3.4.3. Sat(n, CPS) = {Gi V An_6, G2 V A'n_6}, n > 6
Proof. Say G Â£ Sat(n, CPS). One of {Gi, G2} must therefore be a subgraph of G.
If n > 6 then G also contains least one other vertex v. The smaller graph G v
is a split graph, with vertices appropriately partitioned into sets with induced
subgraphs A, a clique, and B, an independent set. Let u be a neighbor of v. If
u is in B then in order for G to be a split graph A U {u} must be a complete
graph. We can also join v to every other vertex in B without destroying either
condition. So, v is is adjacent to every vertex in G {u}. If it is in A then either
< H(A)U{i>} > is a clique, which again implies that v is adjacent to every vertex
in G {u}, or there is a vertex a 6 A such that v a and V(B) U {u} is an
independent set. In this case the edge va can be added to G without violating
the split property, and therefore A U {u} must be a clique. Hence v is adjacent
to every vertex in B in order for G to be iPsaturated.
Therefore, Sat(n, Ts) = {Gi V A'n_6, G2 V An_6} when n > 6
3.5 Other Examples
44
Definition 3.5.1. A graph G is a unit interval graph if it has an interval rep
resentation in which every vertex is associated with an interval of length 1.
The following theorem of Roberts [53] will be useful.
Theorem 3.5.2. ^4n interval graph G is a unit interval graph if and only if it
does not contain K13 as an induced subgraph.
Let 7U denote the family of unit interval graphs.
Theorem 3.5.3. Sat(n, 7U) = {Ad,3 V Adi_4, C4 V ATn_4}, n > 4
Proof Let n > 4. We have already seen in Theorem 3.2.2 that C4 V ATn_4 is
an edge maximal noninterval graph. Since the addition of an edge results in a
clique with a single edge removed, which does not contain an induced Ad,3, it is
also in Sat(n, Pu). Ad.3 V Kn_4 is an interval graph, but by Theorem 3.5.2 is not
unit interval. However, any edge added to Ad,3 V An4, (in fact, there is only
one such edge without loss of generality), eliminates the induced Ad,3 without
creating either an asteroidal triple or a large induced cycle. So, this graph is
also in Sat(n, Pu).
Now say that G is a /^saturated graph. Then G must contain either a
large cycle, an asteroidal triple, or a AT1,3 as an induced subgraph. Denote this
induced subgraph J. By Lemma 3.2.1 wre know G cannot contain an asteroidal
triple, and by Theorem 3.2.2 there is no induced cycle with length greater than
4. So, G contains either an induced Ad,3 or an induced C4. If G is not precisely
Ad,3 V A"n_4 or C4 V A'_4, then it is a proper subgraph of one of them. There is
an edge that can be added to G without eliminating J as an induced subgraph.
Hence, Sat(n, 7U) = {Ad,3 V A'n_4, C4 V A"n_4}
45
Figure 3.11: The basic minimally noncircular arc graphs
We now introduce a type of graph often studied alongside interval graphs.
Definition 3.5.4. A graph G is called a circular arc graph if it is an interval
graph of a family of arcs of a circle.
In other words, instead of modeling intervals in the real line, the vertices of
a circular arc graph can be represented by arcs on a circle. Note that all interval
graphs are easily seen to be circular arc graphs by applying an isomorphism
from the real line to the unit circle minus a point.
A graph G is minimally 7 if it has property 7 but no proper subgraph has
property 7. Denote by G* the graph obtained from G by adding an isolated
vertex. We will use the following Lemma from [55].
Lemma 3.5.5. The following graphs are minimally noncircular arc graphs:
bipartite claw, net*, nnet for all n> 3, umbrella*, (ntent)* for all n> 3, and
C* for every n > 4. Any other minimally noncircular arc graph is connected.
46
Figure 3.12: A graph and its circular arc representation
Bonomo et al. refers to the graphs above (see Fig. 3.11) as basic minimally
noncircular arc graphs in [5]. Let 7C denote the family of circular arc graphs.
Theorem 3.5.6. The only Tcsaturated basic minimally noncircular arc graph
is C%.
Proof. It is easy to show that Cl is CPcsaturateed, since the addition of any edge
results in either a C4 with a pendant edge, realizable by the arcs
(0,2.1),(2,4.1),(4,6.1),(6,0.1),(1,1.5)
in radians (Fig. 3.12), or (K4 e) U A"i, which is an interval graph and therefore
a circular arc graph. Now let G be a bipartite claw, net*, nnet or umbrella*.
The addition of the edge ab as labeled in figure 3.11 creates an induced Cl from
the a6path, edge ab, and vertex c. In the ntent if we add the edge joining
vertices 1 and n, then we get an induced Cl from the vertices: 1, d, e, n, and c.
If n > 5 in the C*, then the addition of the edge between vertices 1 and n 2
creates an induced Cl from the vertices: 1, n, n 1, n 2, and c. Therefore, the
only basic minimally noncircular arc graph in Sat(n,7c) is C4.
47
4. Subdivided Graph Saturation
This chapter represents joint work with M. Ferrara, M. Jacobson, K. Milans,
and P. Wenger.
4.1 Introduction
We begin this chapter with some terminology.
Definition 4.1.1. A maximal 2connected subgraph B of a graph G is a block
of G. If B = H for some H, then we will say that B is an Hblock of G.
Definition 4.1.2. If X a cutset of G, then an Xlobe of G is any subgraph
induced by X and the vertices in a single component of G X. An Hlobe of
G is a lobe of G that is isomorphic to H.
We let G~ denote the graph obtained by deleting all of the pendant vertices
of G.
Recall from Chapter 1 that a graph G can be subdivided by the replacement
of edge {x, y} with vertex z and edges {x, z}, {z, y}. We let S(G) represent the
family of all graphs resulting from any number of subdivisions of G, including
G itself.
Definition 4.1.3. Let G be a graph, F e S(G). We can view V(G) as a subset
ofV(F). We call these vertices the branch vertices of F.
The focus of this chapter is to study S(i/)saturated graphs for certain
choices of H with the goal of analyzing the similarities and differences between
48
//saturated and S(//)saturated graphs of minimum size. In particular, we
consider the cases where H is either a clique or a cycle and we obtain a number
of exact results and bounds.
4.2 Cycles
4.2.1 History
Ctsaturated graphs of minimum size have been studied extensively. While
a number of bounds have been determined, very few precise values of sat(n, Ct)
are known. Some known results are summarized in the Table 4.1.
Recall that a graph of order n is hamiltonian if it contains a cycle of length
n.
Definition 4.2.1. A graph G of order n is maximally nonhamiltonian (MNH)
if it is not hamiltonian but the addition of edge {x, y} for any nonadjacent pair
of vertices x, y results in a hamiltonian cycle.
The Coxeter graph [14] is a MNH graph of order 28 and smallest cycle length
7, (Fig. 4.1).
Using an edge coloring argument and Isaacs flower snarks from [39], Clark
Crane, Entringer, and Shapiro determined the exact value of sat(n, Cn) for suf
ficiently large n [12], [13], [11]. It is their method that we enlist in this section.
4.2.2 t <6
We begin by determining sat(n, Â§(Ct)) exactly for t < 6.
We begin by noting that any cycle is a subdivision of C3, and therefore
sat(n, S(Cs)) = n 1 for all n. Next we consider S(C,4)saturated graphs.
49
t sat(n, Ct)
3 n 1 [21]
4 L^J,n> 5 [48, 57]
5 = [y(n 1)],n >11, n g N0 [9] = rf (n 1)1 1, neNo = {11,12,13,14,16,18,20}
l < n + Cj for a constant c, l ^ 8,10, n sufficiently large >(1 + 2/+8 n 1 ^ 5 W
l < (1 + l 0(mod2), l > 10, n > 31 < (1 + j^)n + ^,1 = l(mod2), l > 17, n > 71 [30]
6
7 <^[1]
/ = 8,9,11,13,15 < f + f [30]
n even or n > 17 odd [4, 11, 12, 13, 44]
Table 4.1: Known bounds and and exact values for sat(n, Ct)
A (1, 3)tree is any tree T in which all vertices of T have degree either one
or three. Let Tn be the family of graphs of order n > 3 vertices generated by
simultaneously performing A Y exchanges on all of the vertices of degree three
in T, and then deleting up to three pendants. An example of a member of this
family can be seen in Figure 4.2. We note here that every T Jn has size
t(n) = n+ L^J.
The following Lemma is a consequence of the elementary fact that any 2
connected graph of order at most four contains a cycle of length at least four,
50
Figure 4.1: The Coxeter graph
Figure 4.2: A (l,3)tree and the associated graph in Ti8.
along with the observation that every block of a S(C4)saturated graph must
also be S(C,4)saturated.
Lemma 4.2.2. If G is a $(0^)saturated graph, then every block ofG is a clique
of order at most three.
We also require the following Lemma, which suffices to establish that any T
in 7n is S(C<4)saturated.
51
Lemma 4.2.3. If G is a graph satisfying both of the following two properties
then G is S(C4)saturated.
1. Every block of G is isomorphic to either K2 or K%, and
2. no two K2blocks of G share a vertex,
Proof Let G be as given in the statement of the Lemma and let u and v be
nonadjacent vertices in G. Properties (1) and (2) imply that, regardless of the
choice of u and v, there is a u v path of length at least three in T, implying
that T + uv has circumference at least four.
Theorem 4.2.4. For n > 1, sat(n, Â§(64)) = t(n) = n + .
Proof The upper bound follows from Lemma 4.2.3, as any T G Tn is S(C4)
saturated, as are Ki and K2.
To establish the lower bound, let G be an S(C*4)saturated graph of minimum
size. The Theorem holds if n < 3, since in this case G must be a clique so we
may assume that n > 4. Lemma 4.2.2 implies that G must have more than
one block, so first suppose that xy and xz were distinct A'2blocks of G. Then
each block of G + xy must still be either a K2 or a K3, implying that G cannot
contain a cycle of length at least four, and hence that G is not S(C4)saturated.
Thus, no two ^blocks of G share a vertex.
Next, assume that J and K are A'3blocks of G sharing a cutpoint x, and
furthermore that for some vertex y, xy is an endblock of G. Then we can remove
y and expand x to a K2 without increasing the size of G. If x does not lie in a
A2block of G, but there is some other pendant vertex y in G, then we can again
52
delete y from G and expand x to a A'2 without increasing the order or size of G.
If G does not contain any pendant vertices, then G contains distinct endblocks
B and B' isomorphic to K:i. We can therefore expand x to a A'2) remove two
noncutvertices from B and add a pendant vertex to a noncutpoint vertex of
B'. Lemma 4.2.3 implies that, throughout each of these operations, G remains
Â§(C,4)saturated. Therefore, we can assume that k(G) = 1 and each cutpoint
in G is contained in a AT2block and a A'3block of G.
If G contains two endblocks isomorphic to K3, then by removing the two
noncutpoint vertices of one and adding pendant vertices to each of the noncut
point vertices of the other results in an S(C4)saturated graph with the same
order as G and fewer edges, contradicting our minimality assumption. Thus,
we can also assume that G contains at most one endblock isomorphic to A'3.
Together with the previous assumptions, we conclude that G 6 T, completing
the proof.
We now turn our attention to Â§(Gs) and S(Ce)saturated graphs. Our
technique for determining the saturation numbers of these families is similar to
that employed in Theorem 4.2.4. We call Bt = A2 V Kt, a book. We refer to
the edge uv that is joined to the maximum independent set as the spine of the
book, and to the t vertices in the independent set as the pages of the book.
Lemma 4.2.5. If G is a 2connected S(C5)saturated graph of order n that is
not a clique, then n > 5 and G = i?_2.
Proof Suppose first that G is 3connected. Since G is not a clique, then G must
have order at least five. If G has order strictly greater than five, then Mengers
53
Theorem and a result of Chvatal and Erdos [12] imply that G must contain a
cycle of length at least six. Hence we conclude that G has order exactly five,
and since 6(G) > 3, Diracs Theorem [16] implies that G is hamiltonian, again
a contradiction.
Hence we conclude that k(G) = 2 and consider a minimum cut set X =
{x,y} in G. Each Alobe of G must contain an x y path of length at least
two. If any of these paths had length more than two, then G would contain a
cycle of length at least five. Since G contains no cut vertices, we conclude that
each Adobe has order exactly three, and hence that G is isomorphic to either
Bn2 or A'2,n_2 Since adding the edge xy in the latter case does not create a
cycle of length at least five, we conclude that G = 5_2, as desired. As B\ = A3
and B2 = Ki e are not S(Cs )saturated, we conclude that n > 5.
Lemma 4.2.5 implies that every block of an S(C5)saturated graph is either a
complete graph of order at most four or a book with at least three pages. Next,
we consider the feasible placement of AVblocks within an S(C5)saturated graph.
Lemma 4.2.6. Let G be a S(C5)saturated graph and let B = xy be a block of
G isomorphic to AV Then if x is a cutvertex of G, and B' ^ B is a block of
G that contains x, either B' = K4 or B1 = Bt and x does not lie on the spine
of B. Consequently, G xy is also S(C5)saturated.
Proof. Suppose that, without loss of generality, d(x) > 1 and that xz, z ^ y is
an edge in some block of G that is either A'2 or A3. Then in G + yz, the block
containing x, y and z would be either a A3 or a A'4 e. As the remaining blocks
from G would be unchanged, G + yz could not contain a cycle of length at least
54
five, contradicting the assumption that G was S(C5)saturated.
Suppose that xy is a block of G isomorphic to K2 and furthermore that x
lies in a block of G isomorphic to Bt. Then the edge xw cannot be the spine of
the book, as in G + wy, the block containing x,y and w would then be Bt+\.
This again contradicts the assumption that G is S(C5)saturated.
Since each block of G must be S(C'5)saturated, G xy must be S(C5)
saturated if d(y) = 1. If d(y) > 1, then the fact that G xy is S(C5)saturated
follows from several observations. First, the ux,;lobes of G xy must be S(Go)
saturated. Secondly, since xy wras only incident to blocks isomorphic to K4 or
Bt, t > 3, one can readily verify that for any two vertices u and v lying in
distinct components of (G xy) vxy there is a u v path of length at least four
in G uv.
The following Lemma follows easily from Lemmas 4.2.5 and 4.2.6 and states
that, under the restrictions for AVblocks established in Lemma 4.2.6, we may
rearrange the blocks of an S(C,5)saturated graph as needed.
Lemma 4.2.7 (The Rearranging Lemma). Let S denote the family of graphs H
with the following properties:
1. Every block of Bt is either a clique of order at most four or a book with at
least three pages, and
2. for any K2 block B of H and block B' ^ B of H such that B D B' ^ 0,
either B' is a K^block of H or B' is a Btblock of H with t > 3 such that
B C\ B1 is a page of B'.
Then a graph G is S(C5)saturated if and only if G G S
55
We now are ready to determine sat(S(C5), n).
Theorem 4.2.8. For n> 7,
sat(n,S(C5)) = f(n)
/
[f\ In = 0,1,3, 5 (mod 7)
<
[y1] n = 2,4,6 (mod 7)
Proof. We establish the upper bound by using the graphs Hi,..., H6 pictured
in Figure 4.3 to construct S(C<5)saturated graphs Gn of order n for each n > 7.
T
T T
H
o V
H
H
1
H
H.
H.
H.
Figure 4.3: S(C5) builders (subscripts indicate value of n (mod 7))
For 7 < n < 13, we let Gn = Hi+7 for each of the Gj in Figure 4.3. For
n > 14 we construct Gn from Gn_7 by taking a copy of H\ and associating
the vertex v with the vertex in the copy of Hn7 (mod 7) contained in Gn_7 that
is marked with an open circle. It is straightforward to verify that each Gn is
8(65(saturated for each n > 7. We also note that these graphs are not unique.
56
As constructed, the blockcutpoint graph of each G~ is a star with at most one
edge subdivided. It would have been acceptable to assemble the blocks of G~
so that the blockcutpoint graph was, for instance, a caterpillar with a longer
spine.
To establish the upper bound, we proceed by induction on n. It is straight
forward to verify that, given Lemma 4.2.7, the graphs H0,..., Hq serve to estab
lish the base cases of 7 < n < 13. We therefore assume that for all 14 < t < n,
sat(t, S(Cs)) = f(t) and consider G, a S(Gs)saturated graph of order n > 7 and
minimum size. We furthermore assume that e(G) < f(n). Note that G must
be connected, but by Lemma 4.2.5 cannot be 2connected, as e(Bn2) > e(G)
for n > 7. Thus G must have connectivity one, so that each block of G is either
a clique of order at most four or a book with at least three pages. Table 4.2,
which relates the values of f(n) and f(n k) for 0 < k < 6, will be useful as we
proceed.
Suppose first that there is a cut vertex x in G such that some xlobe L is
isomorphic to H\. Then G' = G (L x) is still S(Gs)saturated by Lemma
4.2.6. Then G' has at least f(n 7) edges by the induction hypothesis, and hence
G has at least f(n 7) h 10 = f(n) edges, a contradiction to our assumption
about the minimality of G.
Similarly, now assume that there is some xlobe L that is isomorphic to
H0, and let p ^ x be a pendant vertex in L. Note that Lemma 4.2.6 implies
that G p is S(Gs)saturated, as must be G' = G (L x). Therefore, the
induction hypothesis implies E(G p)\ > f(n 1) and \E(G')\ > f(n 6).
We now consider two possibilities, based on the value of n (mod 7). If n = 1, 3
57
n (mod 7)
0 1 2 3 4 5 6
f(n) ~ 1 f(n) ~ 1 fin) ~ 2 fin) ~ 1 fin) ~ 2 fin) ~ 1 fin) ~ 2
f(n 2) f(n) ~ 3 f(n) ~ 2 fin) ~ 3 fin) 3 fin) ~ 3 fin) ~ 3 fin) ~ 3
/( 3) f(n) ~ 4 f(n) 4 fin) ~ 4 fin) ~ 4 fin) ~ 5 fin) 4 fin) ~ 5
f(n ~ 4) f(n) 6 f(n) ~ 3 fin) ~ 6 fin) ~ 5 fin) ~ 6 fin) ~ 6 fin) ~ 6
/(n 5) f(n) ~ 7 f(n) ~ 7 fin) ~ 7 fin) ~ 7 fin) ~ 7 fin) ~ 7 fin) ~ 8
f{n 6) f(n)~9 Sin) 8 fin) ~ 9 fin) 8 fin) 9 fin) ~ 8 fin) ~ 9
Table 4.2: f(n k), 0 < k < 6, listed by value of n (mod 7).
or 5 (mod 7), then Table 4.2 gives that f(n 1) = f(n) 1. Thus, Â£'(G!) =
E(G p) \ + 1 > f(n 1) + 1 = fin), a contradiction. Similarly, if n = 0, 2, 4
or 6 (mod 7), then f(n 6) = f(n) 9. Consequently, in this case, \E(G)\ =
lE^G')! + 9 > f{n 6) + 9 = fin), again a contradiction. Hence we may assume
that G has no Ho or LAlobe.
We can also use Table 4.2 to show that G has no A'3 or AVlobes. Suppose
otherwise, so that there was some cutvertex x in G such that the vertices
x, y and z formed a AVlobe of G. By the Rearranging Lemma, G {y, z} is
still S(Cs)saturated. However, by the induction hypothesis, E(G {y,z})\ >
f(n 2) and by Table 4.2, f(n 2) > /(n) 3. Consequently, \E(G)\ 3 =
\E(G {y, z})\ > f(n 2) > f(n) 3, a contradiction. Hence G has no AVlobe.
As f(n 3) > f{n) 5, a nearly identical argument demonstrates that G also
has no AVlobe.
58
We require a bit more terminology as we proceed. By an extended book we
mean a book with at most one pendant adjacent to each page (for instance, H0
and Hi are both extended books). The spine of an extended book is defined
analogously to that of a traditional book, and we refer to both a point joined
to the spine or a A'2block as a page of an extended book. Additionally, by an
endlobe of G we mean and endblock B of G~ together with some or all of the
pendants in G that are adjacent to a vertex in B.
Figure 4.4: Exceptional K,itype Lobes
Consider the graphs So and Si depicted in Figure 4.4. If some maximal end
lobe L is isomorphic to Si, then by Lemma 4.2.6, there is no block of G that is
both isomorphic to AT2 and incident to x, save for the one contained within L.
Consequently, we may replace L with a copy of Hi, where x is one of the vertices
on the spine of H\. Similarly, if there is some maximal endlobe L isomorphic
to So, then we can replace L with a copy of Hq, again with x playing the role of
one of the vertices on the spine of Ho. Either of these operations wrould result
in an S(C5)saturated graph with the same order and size as G that contains a
previously prohibited lobe. This implies that neither S0 nor Si are lobes of G.
Suppose that some endlobe L of G is isomorphic to an extended book with
59
t > 3 pages and suppose as well that L is a maximal such endlobe. By the
rearranging Lemma, we may assume that a vertex x on the spine of L is the
cutvertex that separates L from the rest of G. If t > 3 and fewer than t 1 of
these pages have pendants, then replace L with an extended book V having one
fewer page and one more pendant. The resulting graph is still S(C5)saturated,
has order n, and has fewer edges than G. Hence, if t > 3, we may assume
that either t 1 or t of the pages of L contain pendant vertices. We may
modify G by deleting one of the leaves of L that contains a pendant and then
adding vertices xi,x% and the triangle X\X2X to G. This rearrangement results
in a S(Cs)saturated graph with the same order and size as G that contains a
AVlobe, contradicting our above assumption.
Hence we may assume that any endlobe of G that is isomorphic to an
extended book with at least three pages must have exactly three pages, at most
one of which contains a pendant vertex. Suppose first that G has some endlobe
L isomorphic to a book with exactly three pages and one pendant edge. If we
let x be the cutvertex of G that separates L from the rest of the graph and
G' = G (L x) then G' is still S(C5)saturated (by the Rearranging Lemma)
and Â£'(G;,) = 8. However, the induction hypothesis then implies that
\E(G')\ > f(n 5) which by Table 4.2 is at least f(n) 8, so that Â£'(G!) > f(n),
a contradiction. Note as well that A4 with one vertex adjacent to a pendant
has order five and size eight, so that an identical argument also allows us to
eliminate this graph as an endblock of G.
It remains to consider only the possibility that every endlobe of G is either
B3 or A'4 with pendants attached to two vertices. However, in a manner similar
60
to our arguments above, if some endlobe of L of G is B3, then the fact that
f(n 4) > f(n) 6 contradicts the assumption that \E(G)\ < f(n). Similarly,
if L was a K with a pendant adjacent to exactly two of its vertices, then the
fact that f(n 5) > f(n) 8 again facilitates a contradiction. This completes
the proof.
Next we determine sat(S(Ce),n). The technique is quite similar to that
used to prove Theorem 4.2.8, so we will omit most of the detail in the interest
of concision.
Let Et be the the graph K2 V (Kt U K2). Some examples are depicted in
(Figure 4.5). We call Et an extended book and use the terms spine and pages in
a manner similar to our description of Bt.
Figure 4.5: The graphs E3,E'3, and Ef
Our next three Lemmas are analogous to Lemmas 4.2.5, 4.2.6 and 4.2.7.
Lemma 4.2.9. If G is a 2connected Â§>(Cq)saturated graph of order n that is
not a clique, then n > 6 and G = En4.
Lemma 4.2.10. Let G be an S(Ce)saturated graph and B = xy a block of G
isomorphic to K2. If x is a cut vertex ofG and B' B is a block of G containing
x, then either B' = Et and x not on the spine of B1, or B1 = K5. Furthermore,
G xy is also &(CÂ§)saturated.
61
Lemma 4.2.11. Let S denote the family of graphs H with the following prop
erties:
1. Every block of H is a clique of order at most 5 or a copy of Et with t >2,
and
2. For any K2 block B of H and block B' B of H, B fl B' ^ 0, either B'
is a K5block of H or B' is an Et block of H with t > 2 such that B D B'
is a nonspine vertex of B'.
Then, a graph G is S(Ce)saturated of and only if G 6 Q.
We are now ready to determine sat(n, B(Ce).
Theorem 4.2.12. For n > 9, sat(n, S(Ce)) = g(n) = ("^] 1.
Proof. Let E[ be Et with a vertex pendant to each nonspine vertex, and let E"
be E[ with a single pendant vertex removed. See Figure 4.5b,c for examples.
For 9 < n < 17 we let the graphs E'2,..., E'5 and E'f,..., E'f be our base cases
and we will proceed by induction on n.
We begin by addressing the base cases, for each value of n, 9 < n < 17,
assume G is an S(C6)saturated graph on n vertices of minimum size. If G were
2connected then it must be the graph En, which has more than g(n) edges.
Hence, in each case we can assume that G has connectivity 1.
Consider the xlobes Â£ of G where a: is a cutpoint. If Â£ is composed entirely
of cliques and, possibly, copies of K5 with pendant vertices attached, then its
size is at least g(n). So, we can assume that G contains at least one xlobe L
isomorphic to Et with a number, possibly zero, of pendants attached to unique
62
nonspine vertices. If a block of G is a A'3 then this block can be replaced by
a page with a pendant added to L without increasing the size of G. Similarly,
if G contains a block isomorphic to A'4 or A'5 with pendants then the block can
be replaced by pages, all but possibly one attached to a pendant vertex, added
to L, with the resulting graph also S(Ce)saturated but of smaller size. So, for
9 < n < 17, sat(n, S(C6)) can be realized by one of E2,..., E'5 or E2,..., Ag.
Let n > 9 and for all t,9 < t < n, sat(t,S(Ce)) = g(t). Now assume that
there is some S(Ce)saturated graph G of order n with e(G) < g(n). We will
consider possible endXlobes of G.
Case 1: G has an endlobe L isomorphic to K3. By Lemma 4.2.11, G (L x) is
S(C*6)saturated, n(G (L x)) n 2, and e(G (L x)) < e(G) 3 <
g{n) 3 = gin 2), contradicting our inductive assumption.
Case 2: G has an endlobe L isomorphic to X4 but none isomorphic to K3. n(G
(Lx)) = n 3,e(G(Lx)) < e(G)6 < g[n) 6 = g(n4) < g(n3),
again contradicting the inductive assumption.
Case 3: G has an endlobe isomorphic to K5 with i pendant vertices, 0 < i < 5,
but does contain an endlobe like those in cases 1 or 2. n(G (A x)) =
n{4+i),e(G(L x)) < e(G) (10N) < g{n) (10+i) < g(n(4+i)),
once again contradicting the inductive assumption.
Case 4: G has endlobes isomorphic to Et with i pendant vertices, 0 < i < (t + 2),
but does not contain an endlobe like those in the previous cases. Let L be
the lobe with the least i among those with the least t. n{G (L x))
n (t + 4 + i), e(G (L x)) < e(G) (6 + 2t + i) < g{n) (6 + 2t + i) =
63
g{n2) (2t+i) < g(n(t+A+i)), contradicting our inductive assumption
a final time.
4.2.3 General Bounds
The main result of this section is as follows.
Theorem 4.2.13. For t >9, there exists a constant c(t), tending to zero as t
tends to infinity, such that < sat(n,S(Ct) < ( + c(t))n.
The following Lemma allows us to establish the lower bound in Theorem
4.2.13.
Lemma 4.2.14. If G is a 2connected graph of order n > 6 such that every
2cut of G is complete, then e(G) > n.
Proof. If 8(G) > 3 then e(G) > n. Thus we may assume that k(G) = 2 and
that G contains at least one vertex of degree two. For convenience, through the
remainder of the proof we let 7 denote the property every 2cut is complete.
We argue that if G has property 7 and x is a vertex of degree two in G,
then G x also has property 7. Suppose that there is a vertex x of degree twro
in G and note that, as x is a vertex of degree two in G, its two neighbors form
a cutset and are therefore adjacent. If G x does not have property 7, then
G x either is disconnected or contains an independent cutset B of size at most
two.
If G x is disconnected, then the two neighbors of x belong to the same
component of G x, and G is also disconnected, a contradiction. Assume then
64
that G x is connected and that B is an independent 2cut of G. This implies
that the two neighbors of x belong to the same 5lobe of G x, and hence that
B is an independent 2cut in G. This contradicts the assumption that G has
property IP. Therefore deleting a vertex of degree two preserves property CP.
Let G be a 2connected graph with property CP on at least six vertices. We
may inductively remove vertices of degree two from G until we have a graph
G' that contains no vertices of degree two. Thus G' has minimum degree 3 or
is a single edge. If G' has minimum degree three, then m{G') > n(G'), and
each vertex in G that is not in G' contributes exactly two edges to the edge
count for G. Thus n(G) > n(G). If G' = K2, then m{G) = 2n(G) 3. Thus
n(G) > n{G) if n(G) >6.
Theorem 4.2.15. Let t and n be integers such that t > 6 and n is sufficiently
large. If G is a S(Ct)saturated graph of order n, then m(G) > n.
Proof Let n = V((j) and m = 5(G). If G has connectivity k > 3, then
5(G) > 3, and m(G) > n. Thus we may assume that k(G) < 2.
Let A = {x, y} be a minimal 2cut in G. If x and y are not adjacent, then
G + xy contains a cycle of length at least t containing xy. Because A is a cutset
of size 2, all the vertices in the cycle are in one ^4lobe of G. Thus there is an
xj/path P of length t 1 in an ^4lobe. Because A is a minimal cut, x and y
both have a neighbor in each component of G A, so there is an xypath in
each Alobe of G. Joining one of these to P completes a cycle of length at least
t. It follows that every 2cut in G contains an edge. Consequently, if n(G) > 2
then G has property IP, and the result follows directly from Lemma 4.2.14. We
therefore assume that k(G) = 1.
65
Define a big block of G to be a block which contains at least 4 vertices and a
small block to be a block with at most three vertices. Note that two small blocks
cannot be incident, as an edge joining these two blocks would not complete a
cycle of length at least 6. Also, any block with fewer than t vertices must be
complete.
Let l be the number of leaves in G, consider the block decomposition of G~.
Suppose that that there are j large blocks in G~, and note that each large block
B contributes at least 3n(B)/2 edges to G' by Lemma 4.2.14. The large blocks
are either incident or are joined by small blocks, and a vertex v in which is
not in a large block must be in a A'3block B'. Since B' contains either one or
two cut vertices, the vertex v contributes either 3/2 (if B' has exactly one cute
vertex) or 3 (if B' has two cut vertices) to the edge count of G~. Thus e(G~) is
at least 3^"2~^.
Consequently, we know that e(G) is at least 3n~ + t. As no two small
blocks can be incident to the same cut vertex, we know that Â£ < n/2 so it
follows that G has size at least (3/2)n (l/4)n = (5/4)n.
We now show that sat(n,B(Ct)) gets arbitrarily close to the lower bound
given in Theorem 4.2.15 as t tends to infinity. Our strategy is to modify several
constructions developed by Clark, Entringer, and Shapiro in [12] and [13].
Definition 4.2.16. Let G be a 3regular graph and let e G E{G) and {ui, v
V(G). The graph G(e) is obtained from G via the addition of a vertex z adja
cent to the endpoints of e. The graph G(vi,V2, ,Vk) is obtained from G via
the execution of a A Y exchange at each Vi We let G(vi,V2,..., v^, e) denote
G(e)(vi, ^2, Vk). For some examples, see Figure f.6.
66
V
Figure 4.6: A graph G and the modifications G(e) and G(v,e)
One of the best current estimates for sat(n, Ct) comes from a construction
using Isaacs family of snarks[39].
Definition 4.2.17. Let m > 3 be an odd integer. Let Jm denote the graph with
V(Jm) = {vi : 0 < i < 4m 1},
and
E(Jm) = E0 U E1 U E2 U E3
where
Eo = {{v4j,v4j+1}, {v4j,v4j+2}, {v4j,v4j+3} ()<]< m 1},
El = {{v4j+i,v4j+7} : 0 < j < m 1},
E2 = {{vAj+2, v4j+6} : 0 < j < m 1}, and
E3 = {{%+3,v4j+5} :0
All subscripts are taken modulo Am.
Definition 4.2.18. Let Gi, G2, ., Gk be graphs, and let u4 E G\,u2 6
G2,...,Uk Gk be vertices. The graph resulting from a copy of G\, copies
of Gi Ui for 2 < i < k, and all edges between u4 and the vertices in Gi
67
that are adjacent to Ui in Gi, 2 < i < k, is referred to as identification at
{ui,u2, ,uk}.
The following were developed in [1].
Definition 4.2.19. Let G be a graph. The graph H is a Gbuilder if H is
Gsaturated and the graph resulting from identifying multiple copies of H at a
vertex v in H is also Gsaturated. For a family T of graphs define an Tbuilder
similarly.
Using this notion, Barefoot et. al were able to show the following:
Theorem 4.2.20. For n > Am > 12, m odd, sat(n, Cm) < 'g^f jn + 2m.
The C4mbuilder H^m used to prove Theorem 4.2.20 is a copy of Jm with
the addition of pendant vertices to every vertex save Vo, as shown in Figure 4.7.
These builders are then associated at v0 to form the desired saturated graph of
small size.
Figure 4.7: The graph J3 and a Ci2builder based on it
This construction, at first, seems less than optimal in light of the results in
Table 4.1 which show that sat{Ct, n) approaches n as t grows large. However, of
68
interest here is the observation that any graphs G constructed from the builders
tf4mvia association at vq are also S(C,4m)saturated, as each block in such a G
has order at most 4m and circumference at most 4m 1. This observation is
key, and we will use modifications to Issacs snarks to construct S(Ct) graphs
similarly.
A graph G of order n is maximally nonhamiltonian if G is not hamiltonian,
but for any pairs of nonadjacent vertices x and y in G, G + xy is hamiltonian.
Theorem 4.2.21. 1. Let e = {uo,^}. For m > 5 the graph Jm(e) is maxi
mally nonhamiltonian.
2. For m > 5, Jm(v2) is maximally nonhamiltonian.
3. Form > 7, Jm(v4,vu) is maximally nonhamiltonian.
4. Form > 9, Jm(v2, ^14,^26) is maximally nonhamiltonian.
5. For m > 9, Jm(v 14, e), Jm(v 14, v2e, e), and Jm(vu, v2g, v38, e) are maximally
nonhamiltonian.
We combine the constructions from Theorems 4.2.20 and 4.2.21 to achieve
an upper bound for sat(n,S(Ct)) for all sufficiently large t. A graph G is
hamiltonianconnected if for every pair of vertices u,v G G there is a hamil
tonian path from u to u. G is maximally nonhamiltonianconnected if G is not
hamiltonianconnected but for any pair of nonadjacent vertices u and v in G,
G+uv is hamiltonian connected. The following Theorem from [40] will be useful.
Theorem 4.2.22. Letm >7 be an odd integer. Jm is maximally nonhamiltonian
connected.
69
For ease of reference we will group to the modified snarks in the following
way. As above, and for the remainder of this section, let e = v$v2 and let z be
the vertex in Jm(e) Jm.
dm = {Jmi Jm{y&i ^14 ) Jm{^2i ^14 > ^26 ) }
dm = {Jm(vUi e), Jm(v 14, v26, e), Jm(vu, v26, v38, e)}
dm = dm U dm
We combine the constructions from Theorems 4.2.20 and 4.2.21 to achieve an
upper bound for sat(n, S(Ct)) for all sufficiently large t.
Lemma 4.2.23. Let G be a 3regular maximally nonhamiltonian graph. Let xy
be an edge of G such that either N(x) y or N(y) x are independent. Then xy
is on a cycle of length n(G) 1 in G. Furthermore, for any edge e G G,e ^ xy
such that G(e) is maximally nonhamiltonian, xy is on a cycle of length n(G) in
G(e).
Proof. Suppose xy is an edge in G with N(y) = {x, yi, y2} and yx not adjacent to
y2. Since G is maximally nonhamiltonian there is a path P of length n(G) 1
between yx and y2. Since y has degree 3 and lies on P, and yxyy2 is not a
subpath of P, the edge xy must be on P. Therefore, either P = yxyxPxy2 or
P = yxP\xyy2 for some path Px in G, (see Figure 4.8). In the former case
yxPxy2y is an (n(G) l)cycle in G, and in the latter the cycle y\P\xyyx has
length n(G) 1. In both cases the edge xy is on an (n(G) l)cycle in G. If
G(e),xy 7^ e, is maximally nonhamiltonian we can utilize a hamiltonian path in
G(e) of length n(G) between yx and y2 to construct an n(G)cycle containing
xy.
70
Figure 4.8: Every edge in a modified snark is on a long cycle
Lemma 4.2.24. Let m > 9 be an odd integer and let J be a graph in dm Let
u, v, w be vertices in J, with u and v not necessarily distinct. There exists a
u w path Pi and a v w path P2 in J such that the total length of Pi and P2
is at least n(J).
Proof. Let Pi be a longest u w path in J. Note that every edge in J, except
e = Vqv2 and the edges vqz,zv2 created in Definition 4.2.16 if J Â£ dm, satisfies
the requirements of Lemma 4.2.23 since {v2, n14, v2q} and {v^, v2q, ^33} are inde
pendent sets of vertices in Jm for m > 9. However, if J E dm the path VoZV2 can
replace the edge e in an n(J) 2 path to create an n(J) 1 path in J. So, e is
the only edge in J not necessarily on a cycle of length n( J) 1. If u is adjacent
to w and uw e or J Â£ dm then by Lemma 4.2.23 uw is on an n(J) 1 cycle.
If uw = e and J E dm then uw is on an n(J) 2 cycle in J. Otherwise, since
J is maximally nonhamiltonian there is a hamiltonian path between u and w.
Therefore, Pi has length at least n(J) 2. Similarly P2, a longest v w path in
J, has length at least n(J) 2, implying that the sum of the lengths of Pi and
P2 is at least 2n(J) 4 > n(J).
We now construct a family of S(C'i)saturated graphs.
Theorem 4.2.25. Let m > 9 be an odd integer and let J G dm The graph
resulting from adjoining at most one pendant vertex to all vertices of J other
than v0 and v2 results in an S(Cn(j))saturated graph. Similarly, if H G dm then
the graph resulting from adjoining at most one pendant vertex to all vertices of
H results in an Â§>(Cn(H))saturated graph.
Proof. Let J G dm Since J is maximally nonhamiltonian by Theorem 4.2.21,
J is also S(C'T1(>/))saturated. Also, as the addition of pendants to J does not
increase the circumference of J, it suffices to prove that the graph J' obtained by
adding a pendant vertex to each vertex in V(J) {fo, ^2} is S(C'n(j))saturated.
Since J does not contain a subdivided Cn(j), neither does J'. Because J
is S((7n(j))saturated by Theorem 4.2.21, we need only consider the addition of
edges to J' with at least one endpoint in J' J. Let r be a pendant vertex in J'
with neighbor x. Let y be a neighbor of x distinct from r and first consider the
addition of the edge ry. The edge xy lies on an n(J) 1 cycle in J' by Lemma
4.2.23, so replacing the xy with the path xry in J' + ry results in an n(J) cycle.
Next, we consider J' + rw where w is not adjacent to x. Note that if xw is
added to J' an n( J)cycle C results by Theorem 4.2.21. If rw is added instead,
a cycle of length n(J) + 1 results from C by replacing the subpath wx with wrx.
Similarly, if r\ is another pendant vertex in J' with neighbor w not adjacent to
x, then the addition of edge rr\ results in a cycle with length 2 greater than the
n(J) cycle containing xw in J + xw. Finally, if r2 is a pendant vertex adjacent
to y G N(x) then the cycle of length n(J) 1 in J' that includes xy, assured by
Lemma 4.2.23, can be extended to a cycle of length n(J) + 1 by replacing the
edge xy with the path xrrpy. Therefore, J' is S(C'n(j))saturated.
72
In a similar manner, we can create S(Cn(//))saturated graphs by adjoining
at most one pendant vertex to all vertices of H e 3^ other than v0. Due to the
similarities, we omit the proof here.
Note that, for J 6 dm we do not add pendant vertices adjacent to either no
or v2. To see why, consider the case in which r is a pendant vertex adjacent to
v0. Since both v0 and v2 are adjacent to z, the addition of edge rv2 does not
create a cycle any longer than any cycle in J that contains the path v0zv2. The
same is true for any vertex pendant to v2. Since J' does not already contain an
n( J)cycle, neither would J' + rv2.
Lemmas 4.2.23 and 4.2.24 and Theorem 4.2.25 yield the following Corollary.
Corollary 4.2.26. Every graph G 6 3 is a S{Cn(G))builder.
Denote by Gv the graph obtained by adding a single pendant vertex adjacent
to each vertex of a graph G other than v. Let n, r and s be integers such that
0 < r < n(G) 1, n > 1 and n = r + s(2n(G) 1) + 1. Denote by GTV S a graph
on n vertices composed of s copies of Gv and and a single copy of Grv identified
at v. By Corollary 4.2.26, if G is one of the possibly modified Jms from above
then Grv s is SCt saturated for t = n(G).
We now determine upper bounds on sat(n, S(Ct)) for sufficiently large t.
Theorem 4.2.27. Let m > 9 be an odd integer.
/ w 10m 1 sat{n, S{C4m)) < 2 n + 2m (4.1)
1 Dm, + 1
sat(n, S(C4m+i)) < n gm 1 + 2m + 1 (4.2)
1 Dm 13
sat{n, S(C,4m+2)) ^ n gm + 2 +2m (4.3)
73
sat(n, Â§(C4m+3)) < + 2m + 2 (4.4)
\ Q jll ) 9
sat(n,S(C4m+i))
8 m + 6
sat(n, Â§{Cim+5)) < w ^ 7^ + 2m + 3 (46)
sat{n, Â§{C4m+6)) < n + iq + 2m + 3 (4.7)
sat(n, S(C4m+7)) < + 2m + 4 (4.8)
Proof. The proof of (4.1) is from [1], and we reproduce it here to demonstrate
how each equation in the Theorem is obtained. Let G be the graph obtained by
adding a pendant vertex to every vertex in Jm other than u0 n(G v0) = 8m 2,
so construct the graph G(4m,n) by associating s = ~8^_12] copies of G at vq
and deleting r = 1 + s(8m 2) n pendants. Note that 0 < r < 8m 3. By
Corollary 4.2.26 G(4m, n) is S(C4m)saturated and has order n = l+s(8m2)r
and size s(10m 1) r = x^~2 (re 1) + "^f}2r < 8m 2 n 2m. Therefore
sat(n, S(C4m)) < ^fdn + 2m.
To establish (4.2) let G be the graph obtained by adding a pendant vertex
to every vertex in Jm(e) other than v0 and u2. Construct G(4m + l,n) by
associating s = copies of G at v0 and deleting r = 1 + s(8m 1) n
pendants. By Corollary 4.2.26 G(4m +1, n) is S(C4m+i)saturated and has order
n = 1 + s(8m 1) r and size s(10m + 1) r < g0n + 2m + 1.
To establish (4.3) let G be the graph obtained by adding a pendant vertex
to every vertex in Jm{v2) other than v(). Construct G'(4m + 2, n) by associating
s = f^l copies of G at vq and deleting r = 1 + s(8m + 2) n pendants.
By Corollary 4.2.26 G(4m + 2, n) is Su6(C4m+2)saturated and has order n =
1 + s(8m + 2) r and size s(10m + 3) r < + 2m.
74
To establish (4.4) let G be the graph obtained by adding a pendant vertex
to every vertex in Jm(v 14, e) other than v0 and u2. Construct G(4m + 3,n) by
associating s = copies of G at u0 and deleting r = 1 + s(8m + 3) n
pendants, is S(C4m+3)saturated and has order n = 1 + s(8m + 3) r and size
s(10m + 6) r < n + 2m + 2.
To establish (4.5) let G be the graph obtained by adding a pendant vertex to
every vertex in Jm(u4,u 14) other than v0. Construct G(4m + 4,n) by associating
s = copies of G at v0 and deleting r = 1 + s(8m + 6) n pendants.
By Corollary 4.2.26 G(4m + 4, n) is 5'u5(C4m+4)saturated and has order n =
1 + s(8m + 6) r and size s(10m + 9) r < g0^^9 + 2m + 7.
To establish (4.6) let G be the graph obtained by adding a pendant vertex
to every vertex in Jm(vu, V26, e) other than v0 and u2 Construct G(4m + 5, n)
by associating s copies of G at v0 and deleting r = 1 + s(8m + 7) n
pendants, is S(C4m+5)saturated and has order n = 1 + s(8m + 7) r and size
s(10m + 11) r < + 2m + 3.
To establish (4.7) let G be the graph obtained by adding a pendant vertex
to every vertex in ^(^2^14,^26) other than v0. Construct G(4m + 6,n) by
associating s = [5^75] copies of G at vq and deleting r = 1 + s(8m + 10) n
pendants. G(4m + 6, n) is S'u5(C,4m+6)saturated and has order n = 1 + s(8m +
10) r and size s(10m + 14) r < + 2m + 3.
To establish (4.8) let G be the graph obtained by adding a pendant vertex to
every vertex in Jm{vu, u26, u38, e) other than uo and u2. Construct G(4m + 7, n)
by associating s = r111 copies of G at vq and deleting r = 1 +s(8m + ll) n
pendants. G(4m + 7, n) is S(C4m+7)saturated and has order n = 1 + s(8m +
75
11) r and size s(10m + 16) r < g0^^6n + 2m + 4.
The reader should note that (4.5), and (4.7) may be improved slightly by
the addition of a single vertex pendant to v0 after associating the copies of
Jm(v4,n14) and Jm(u4, vu, V2%) respectively in the construction of G(t,n) but
this does not affect the asymptotics of our result.
4.3 Complete Graphs
In this section, we consider S(A't)saturated graphs. Since every subdivision
of K3 is a cycle, it follows that sat(n, K3) = sat(n, S(Ks) = n 1. The follow
ing Theorem of Dirac [15] is central to our characterization of S^A'^saturated
graphs.
Theorem 4.3.1. If 6(G) > 3 then G contains a subdivision of K4.
Lemma 4.3.1 implies that any S(A"4)saturated graph has minimum degree
at most two and it is in fact an exercise in [58] to show that the maximum
number of edges in a graph of order n containing no member of S(A'4) is 2n 3.
We are able to prove a much stronger result characterizing the class of 8(AT4)
saturated graphs. A ttree is any graph that can be obtained from a Kt by
repeatedly adding tsimplicial vertices.
Theorem 4.3.2. A graph G of order at least two is &(KA)saturated if and only
if G is a 2tree.
Proof. We demonstrate that an arbitrary 2tree G is S(A4)saturated by induc
tion on \G\. The base cases G = 2 and G = 3 are immediate, as A"2 and
76
A3 are vacuously S(A4)saturated. Suppose then that G > 3 and let v be a
2simplicial vertex in G and let N(v) = {x,y}. Then the graph G' obtained
by removing v from G is a 2tree, so by induction G' is S(A'4)saturated. The
addition of v to G' cannot contain a subdivision of A4, as such a subdivision
would necessarily contain xvy within some edgepath. Since xy G G', replacing
xvy with xy would yield a subdivision of A"4 within G', a contradiction to the
assertion that G' is S(AT4)saturated. It remains to show that for any vertex u in
G N[v], G + uv contains a subdivision of K4. Any 2tree of order at least three
is 2connected, so Mengers Theorem implies that there are internally disjoint
paths from u to {x, y} in G'. These paths, along with the edges xy, xv, yv and
uv for a subdivision of AC4 in G + uv. Therefore G is S(A'4)saturated.
To establish the necessity, suppose that G is a S(A4)saturated graph and
proceed by induction on Gj. The base case, Gj = 2 is immediate, so we suppose
that G > 3. Clearly, G must be connected, so suppose first that G has a cut
vertex x and let y\ and y2 be neighbors of x lying in distinct components of
G x. The A'4subdivision X created by adding y\y2 to G must have all of its
branch vertices in the same lobe of G, since any edge cut in A'4 has at least
three edges. Without loss of generality, assume that the branch vertices X lie in
the component of G x containing yi. We know that yiy2 must be an edge in
X, and therefore there is some edgepath IP of X containing y 1, y2 and x in that
order. We can replace the segment of CP from yi to x with the edge yx, creating
a A4 subdivision in G, a contradiction.
We may therefore assume that G is 2connected and therefore, by Lemma
4.3.1, that there is a vertex v in G with d(v) = 6(G) = 2. Let N(v) = {x,y}
77
and suppose that x and y are nonadjacent. Then there is a A4 subdivision X
in G + xy which contains xy and, as d(v) 2, cannot contain v. However, then
we can replace the edge xy in X with the path xvy, creating a subdivision of
Ki in G, again a contradiction to the assumption that G is S(A'4)saturated.
It now follows that G v is also S(A'4)saturated. Indeed, if the addition of
any edge U\U2 to G, where i,U2 7^ v, created a subdivision of A"4 containing
v, then necessarily this subdivision would have some edgepath containing the
xvy. Since x and y are adjacent, G + U1U2 also contains a subdivision of G that
omits v, implying the desired conclusion that G v is also S(A'4)saturated. By
induction, G v is a 2tree, and the result follows.
As any 2tree of order n has 2n 3 edges, we obtain the following Corollary.
Corollary 4.3.3. For n > 2, ex(n, S(A'4)) = sat(n, S(A'4)) = sat(n, K4) =
2 n 3.
At this stage, it is tempting to conjecture that sat(n,S(Kt)) = sat(n, Kt)
for all t. Our next two constructions demonstrate that this is not the case in
general.
Theorem 4.3.4. Let t > 5 be an odd integer and let n = d(t 1) + r for d > 2
and 0 < r < t 2. Then
a S(At)saturated graph Gt,n, starting with two copies of A't_i, A and B, with
,t 2
= ( 2 (1))n
Proof. Suppose first that r = 0 and furthermore that d 2. We construct
78
V(A) = {<2i,..., at_i) and V(B) = {&i,..., bt_i}. Add a matching that connects
aj to bi for each i, and then remove the edges diai+1, for i 1,3,..., t 2 from
A. For d > 2, replace each edge with a path Pt = dj, a,, af~2, 6j. Then
for each A: between 1 and d 2 connect a* to a* for every j ^ z 1, z + 1 (where
we consider = a^_Y and a* = a). If r > 0, we add vertices vi,...,vr such
that each Vi is adjacent to Oj and a} (or bit if d = 2). For an example when t 5
see Figure 4.9.
Figure 4.9: An S(A'5)saturated graph of order 18. (d = 4, r = 2)
If r = 0 then Gt has only t 1 vertices of degree at least t 1, implying
that Gt,n cannot contain a subdivision of A^. If r > 0, then we observe that
the addition of Vi cannot create a subdivision of Kt if one was not previously
present, as this would imply that in such a subdivision, some an would be a
branch vertex, and both aj6j and a^vAi would lie within distinct edgepaths, an
impossibility. Thus, for all n, Gt,n contains no member of S(Gt,n) as a subgraph.
It remains to show that for any pair of nonadjacent vertices u and v in
V{Gt,n),that Gt,n) + uv contains a subdivision of Kt. Assume that r = 0 and
suppose without loss of generality that u lies on Pi, that is u = a\,b\ or a\ for
some i. For each choice of v that follows, Gt^n + uv contains a AVsubdivision
79
with branch vertices by, b2 &ti and u, using each edge between the vertices
of B as an edgepath, consequently, we will only describe the edgepaths in this
subdivision incident to u. By symmetry we may assume that if u = a\, then
either v = bj or v = a1* where k > i. In other words, referring to Figure 4.9,
we may assume that v lies below u. Note that this assumption implies that
u 7^ bi as the set B induces a clique.
If v lies in Pi, then v 7^ a,1+1 (or, if u = Gq, v 7^ a*) and the edgepaths
incident to u will be uvP\bi, ua\Pzdzd2P2b2, ua\hla3~1 P3a3, uPidiatiPtibti
and ualjPjbj for 4 < j < t 2. If v lies in P2, then the edgepaths incident to u
are uP\bi, uvP2b2, uPiaiatiPtibti and ua^Pjbj for 3 < j < t 2. For v lying
on Pti, we have the edgepaths from u being uPibi,uPiaiat\a2P2b2, uvPtibti
and ualjPjbj for 3 < j < t 2. Finally, when v lies in Pj for 3 < j < t 2,
the edgepaths incident to u are uP\bi, uvPjbj, ua^Pjaja2P2b2, uPiaiat2Pt2bt2
and ucijPjbj for 4 < j < t 2. Some examples of the subdivisions described
above can be found in
We have therefore verified that Gt,n is S(A't)saturated when r = 0. For
r > 1, we proceed by induction on r. As noted above, Gt,n contains no Kt
subdivision, even when r > 0, so we need only consider the addition of edge uvi
to G. Let G' G Vi and consider the A'rsubdivision % formed by adding the
edge udi to G' (which must exist by induction). Replacing the edge d(d in X
with diViU yields a A'tsubdivision in G + uv^, as desired.
Theorem 4.3.5. Let t > 6 be dn even integer and let n = d(t 1) + r for d > 2
80
Figure 4.10: Examples of A'5subdivisions in G(5,18) + uv. Open circles
represent the branch vertices of the subdivisions formed.
and 0 < r < t 2. Then
sat(n, Â§(Kt))
= {t^ + o(l))n.
Proof. As above, we construct an S(A't)saturated graph G(t,n) of the desired
size, starting with d 2 and r = 0. We again begin with two copies of A'(_i,
A and B, with V(A) = {ai,..., at1) and V(B) = {bi,..., 6t_i} joined by the
edges aibi for 1 < i < t 1. we then remove the edges a^, 0203 and a3ai as well
as the edges diai+1 for i = 4,6,..., t 2 and add the edges a^, 02^3 and a$bi.
For d > 2, replace the edges aj6j with a path Pi = at, a},..., af2, bi. Then for
each k between 1 and d 2 connect af to for every j i 1, + 1 (where we
consider Oq = and af = af). If r > 0, we add vertices v\,...,vr such that
each Vi is adjacent to a* and a\ (or bi, if d = 2). For an example when t = 6, see
Figure 4.11.
81
Figure 4.11: G(6, 21), an S(A'6)saturated graph of order 21. (d = 4, r = 1)
The proof that G(t,n) contains no subdivision of Kt is identical to the
argument in the case where t is odd, and hence we have elected not to repeat it
here.
It remains to verify that for any nonadjacent u and v in G = G(t, n), G + uv
contains a ivrsubdivision. As above, we assume that r = 0. In the interest
of concision, we consider only the case where u lies on Pi, as the remaining
possibilities are handled similarly. As above, by symmetry we may also assume
that v lies at or below the same vertical level as u in the drawing depicted in
Figure 4.11. Some examples of the subdivisions created for various choices of u
and v are depicted in Figure 4.12.
For each choice of u and v that follows, the vertices of B will all be branch
vertices of the subdivision formed, with the edges connecting vertices of B serv
ing as edgepaths. The remaining branch vertex will be either u or v, depending
on the situation, and hence we only describe the edgepaths incident to this
vertex. For the remainder of the proof, given a u (respectively v on some Pl}
we let Uk (resp. ), k ^ i, denote the neighbor of u (v) on P*,, provided such a
neighbor exists.
82
Figure 4.12: Examples of AVsubdivisions in G(6,21) + uv. Open circles
represent the branch vertices of the subdivisions formed.
Suppose first that u lies on Pi, so that u = a\ for some 0 < i < d3. If v also
lies in Pi, then v ^ a\+1 and u is a branch vertex, and the edge paths incident
to u are uvP\bi, uPidib2, ua^a^altlPtibti, and ualkPkbk for 3 < k < t 2.
If v lies on P2, we must handle the case where v = b2 differently from the
other possible choices of v. If v = b2, then u ^ a\ will be the additional branch
vertex in the /\tsubdivision including uv, with the edgepaths incident to u
being uPibi, ub2, uPiaiatiPtibti and uukPkbk for 3 < k < t 2. If v ^ b2,
then v is a branch vertex in a A'rsubdivision, and the edgepaths incident to v
are vuP\bi, vP2b2, vP2a2bz and vvkPkbk for 4 < k < t 1.
For v lying on P3, and v 7^ 63, we have v as the branch vertex of the
/^subdivision in G + uv, with vP3a3bi, vuP\aib2, vb3, vv^P^ and vvkPkbk,
b < k < t 1 comprising the edgepaths incident to v.
83
When v G Pj, for 4 < j < t 4, then u is the additional branch ver
tex, u 7^ uj, and the u bi edgepaths for i ^ 3 are uPibi, uPiaib2, uvPjbj,
uujU2utiPtibti and uiikPkbk for 5 < k < t 2. The u b3 edgepath depends
on whether u = a1: in which case v / a3 and the desired edgepath is uaja^P^bz
If u ^ ai, then the desired edge path is simply WM3P363.
84
5. EdgeCritical G, H Colorings
5.1 Introduction
Let G, H be simple graphs, not necessarily distinct, each containing at least
one edge and not both containing exactly 1 edge. We say that a coloring C of
a simple graph F is an edgecritical G,H coloring if it contains no red G nor
blue H, but changing a red edge to blue or a blue edge to red eliminates this
property. We denote by CSat(G,H) the set of colored graphs that are edge
critical G, H, and by csat(G,H) the fewest number of edges over all elements of
CSat(G, H). As a simple example consider G = H = P3, the path on 3 vertices.
Let F also be P3, and G the coloring of F consisting of one red edge and the
other blue. This coloring of F has no monochromatic P3, but reversing the blue
edge results in a red P3 and reversing the red edge results in a blue P3. So,
(F, G) e CSat(P3, P3). Every graph in CSat(G, H) must contain at least one of
G, H as an uncolored subgraph, so F has the fewest number of edges possible for
a graph with an edgecritical P3, P3 coloring. In fact, it is the unique smallest
such graph and the coloring G is the unique edgecritical P3, P3 coloring on P
up to switching the colors. Therefore, csat(Pz, P3) = 2.
Note that CSat(G, H) need not be finite. In fact, a minimum proper edge
coloring of any disjoint union of any number of even cycles and a linear forest
is also edgecritical P3, P3, (see Fig. 5.1). If F has a vertex of degree at least
3 then every 2coloring of P contains a monochromatic P3. So, CSat(P3, P3)
is precisely the set of all disjoint unions of even cycles and linear forests with
proper edge colorings.
85
Figure 5.1: An edgecritical P3, P3 coloring of a graph
Given any pair of graphs G and H, the disjoint union of any collection of
graphs in CSat(G, H) is also in CSat(G, H). Therefore, if CSat(G, H) is not
empty, then it contains infinitely many colored graphs.
Theorem 5.1.1. IfG is a graph with at least 2 edges then CSat(G, K2), CSat(K2, G)
are nonempty and csat(G, K2) = csat(K2, G) = 1.
Proof. Consider the graph K2 colored red. This is an edgecritical G, K2
coloring. Similarly, a blue K2 is an edgecritical K2, G coloring. Since ev
ery element of CSat(G, K2) and CSat(K2, G) must contain at least one edge,
csat{G, K2) = csat(K2, G) = 1.
5.2 Kneser Graphs
Let i,j be integers no less than 3. We will show that CSat(Ki, Kj) is non
empty.
86
1,2
Figure 5.2: The Petersen Graph KG(5,2)
Definition 5.2.1. The Kneser Graph KG(n,k) for n> k > 0 has as vertices
the kelement subsets of {1, 2,..., n) = [n]. A pair of vertices is adjacent if and
only if their associated sets are disjoint.
The Petersen Graph, (Fig. 5.2), is isomorphic to KG(b,2). It is easily seen
that KG[n,k) has (Â£) vertices and is (nfk)regular.
Theorem 5.2.2. Let m,p > 2 be integers. KG(mp 1 ,p) is Kmsaturated.
Proof. We must first show that KG(mp 1 ,p) contains no clique of order m.
Any maximal collection of pairwise disjoint p element subsets of [mp1] contains
m 1 sets, with p 1 elements remaining. Since every clique in KG(mp 1 ,p)
is associated with such a collection we can see that no clique has more than
m 1 vertices. Now, we must show that the addition of any edge between
nonadjacent vertices of KG(mp l,p) creates a Km. If u,v are nonadjacent
vertices of KG(mp 1 ,p) then they must be pelement sets of the form u =
{n0, ni,..., np_i}, v = {no, np,... n2p_2} for {rq}qP_2 Q [mp 1], not necessarily
87
distinct. There are at least mp 1 (2p 1) = (m 2)p elements remaining
unused in [mp 1], and hence there is a collection of m 2 pairwise disjoint p
element sets also disjoint from {n^}^2. This collection corresponds to anm2
clique in the shared neighborhood of u and v, N(u)DN(v). Joining u to v creates
an m clique in KG(mp l,p). Therefore, I\G(mp 1 ,p) is /^saturated.
We use Kneser graphs of this form to create a graph Fy with edgecritical
A'j, Kj coloring C.
Let Fy be the graph with vertices of the form (r, 6), where r is a 2 element
subset of [2i 1] and b is a 2 element subset of [2j 1]. A red edge exists between
(r, b) and (p, (3) when r and p are disjoint but b and j3 are not. Similarly, a blue
edge exists between (r, b) and (p, (3) when b and f3 are disjoint but r and p are
not. Note that Fy is a coloring of the complement of the modular product of
KG{2i 1,2) and KG(2j 1,2).
Lemma 5.2.3. C is an edgecritical Ki,Kj coloring of Fij.
Proof. A red clique in Fy must be associated with pairwise disjoint 2 element
sets of [2i 1] and pairwise intersecting sets of [2j 1], so there can be no
red clique in Fy larger than the largest clique in KG(2i 1). If {sfc}*i_1 is a
collection of pairwise disjoint subsets of [2i 1] then {(s*, {1, 2})}j1 induces a
red i 1 clique, and thus a largest red clique, in Fy. Similary, a largest blue
clique in Fy has order j 1. We must show that reversing the color of any edge
in Fy creates a red I\l or a blue Kj. Consider a blue edge in Fy. It must be
of the form ({rl5 r2}, {fri, 62}) ~ ({c> ^3}, 64}) where r1,r2,r3 are elements
of [2i 1] and 61,62,63,64 are distinct elements of [2j 1], Let {sfc}j2 be a
88
collection of pairwise disjoint 2 element sets of [2i l]\{ri, r2, r3}, which itself
contains at least 2i 4 elements. The collection {(s*., {61, ^3})}1_2 corresponds
to an i 2 red clique in the shared red neighborhood of ({ri, r2}, {61; 62}) and
({n,r3},{63,64}) in Fid. So, if the edge ({r1,r2},{bub2}) ~ ({n, r3}, {63, 64})
becomes red then we get a red Ki in A similar argument shows that a blue
Kj arises when any red edge is turned blue.
Theorem 5.2.4. CSat{Ki,Kj) is nonempty.
Proof. Fij with coloring C as defined above is in CSat(Ki, Kj).
5.3 Some Results
Note that if G, H are simple graphs such that the graph F with coloring C is
in CSat(G, H) then F with coloring C, the complement of C, is in CSat(H, G).
Therefore, we need only consider one of the two sets.
Theorem 5.3.1. csat(K3, Kf) 10
Proof. We begin by proving the lower bound. Say F with coloring C, denoted
(F,C), realizes csat(K3, Kf). Without loss of generality assume that e(B) >
e(R), where B and R are the blue and red induced subgraphs, respectively, of
(F,C). (F,C) contains a triangle with two blue edges and one red. Label the
blue edges 61,62 and the red edge r4 as in Fig. 5.3. The endpoints of 61 must
share a red neighbor, which must be distinct from the vertices of the original
triangle. So, there are red edges r2, r3 with a shared endpoint such that both
are incident with b\. Similarly there are red edges r4, r3 both incident with
62 and sharing an endpoint. These must be distinct from ri,r2,r3 else (F, C)
89
