CYCLE STRUCTURES IN GRAPHS
by
Angela K. Harris
Master of Science, University of South Alabama, 2003
A thesis submitted to the
University of Colorado Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Mathematical and Statistical Sciences
2009
This thesis for the Doctor of Philosophy
degree by
Angela K. Harris
has been approved
by
Ellen Gethner
Harris, Angela K. (Ph.D., Applied Mathematics)
Cycle Structures in Graphs
Thesis directed by Michael S. Jacobson
ABSTRACT
The study of paths and cycles in graphs has long been fundamental in Graph
Theory. One of the most popular questions in this area is determining when
a graph contains a hamiltonian cycle, a cycle containing every vertex of the
graph. We call such a graph a hamiltonian graph. We will investigate two
different aspects of hamiltonian graphs. The first of these is graphs in which the
hamiltonian cycle avoids certain subgraphs, and the second is the cycle lengths
contained in a hamiltonian graph under given conditions.
Let G be a graph and H be a subgraph of G. If G contains a hamiltonian
cycle C such that E(C) fi E(H) is empty, we say that C is an Havoiding
hamiltonian cycle. Let F be any graph. If G contains an //avoiding hamiltonian
cycle for every copy of H in G such that H = F, then we say that G is Favoiding
hamiltonian. We give minimum degree and degreesum conditions which assure
that a graph G is Favoiding hamiltonian for various choices of F. In particular,
we consider the cases where F is a union of k edgedisjoint hamiltonian cycles
or a union of k edgedisjoint perfect matchings. If G is Favoiding hamiltonian
for any such F, then it is possible to extend families of these types in G. We
also undertake a discussion of Favoiding pancyclic graphs.
From there we turn our attention to pancyclic graphs. A graph of order n
is said to be pancyclic if it contains cycles of all lengths from three to n. We
consider hamiltonian graphs with two vertices of high degree sum. We determine
the conditions on this degree sum that assure that the graph is pancyclic. We
also consider what cycles must be present in the graph when the degree sum
condition is reduced.
This abstract accurately represents the content of the candidate's thesis. I
recommend its publication. ^ n
Signed
DEDICATION
ACKNOWLEDGMENT
I would like to thank my advisor Michael S. Jacobson, without whose support
and direction this thesis would not be possible. I would also like to thank my
coauthor, colleague arid friend Mike Ferrara for his help, support and most of
all, for not backing down. Finally, I would like to thank my children for their
patience with me over the last four years.
CONTENTS
Figures ............................................................ viii
Chapter
1. Introduction....................................................... 1
1.1 Prologue........................................................... 1
1.2 Background......................................................... 2
2. Favoiding Hamiltonian Graphs..................................... 10
2.1 FA voiding Hamiltonian........................................... 10
2.2 Favoiding Pancyclicity........................................... 23
3. Cycles in Hamiltonian Graphs...................................... 27
3.1 Absolute Bounds................................................. 28
3.2 Distancedependent Bounds......................................... 34
4. Cycles in Bipartite Hamiltonian Graphs............................ 42
4.1 A.bsoIute Bounds for Bipartite Graphs............................. 43
4.2 Distance Dependent Bounds for Bipartite Graphs.................... 47
5. Conclusion........................................................ 52
References.......................................................... 54
vii
FIGURES
Figure
1.1 A graph and two subgraphs.......................................
1.2 Nonhamiltonian graphs with a2 = n 1...........................
2.1 A graph G with a2{G) < n + k l that is not //avoiding hamiltonian.
2.2 Extending a cycle C to a longer cycle...........................
2.3 Extending a cycle C to a longer cycle...........................
3.1 d(x) + d(y) = 2n 8, but G contains no (n l)cycle.............
3.2 d{x) + d(y) = 2n 8, but G contains no (n l)cycle.............
3.3 d(x) + d(y) = 2n 10, but the pictured graph contains no (n l)cycle
3.4 d(x) + d(y) > n + k, but G has no cycle of length longer than n k
3.5 d(x) + d(y) = n + k 1, but G contains no cycle of length ^4 .
4.1 d(u) + d(v) = 2n 6, but G* contains no cycle of length 2(n 1) .
3
5
12
16
19
31
31
34
40
40
46
1. Introduction
1.1 Prologue
The study of paths and cycles in graphs has long been fundamental in Graph
Theory. On of the most popular questions in this area is determining when a
graph contains a spanning cycle, that is a cycle containing every vertex. Named
for Sir William Rowan Hamilton, this problem traces its origin to the 1850!s.
Research into this problem has led to a number of deep and interesting results.
One of particular interest lies in studying what cycles are contained in hamil
tonian graphs. We begin with a hamiltonian graph and, given some condition
on that graph, investigate other cycles present in the graph.
In this chapter we provide some brief background material on graphs, em
phasizing terminology and notation used in this paper. In Chapter 2 we intro
duce the idea of a hamiltonian cycle avoiding particular subgraphs in a graph
and develop necessary conditions for a graph to contain a set of disjoint hamil
tonian cycles that avoid a family of subgraphs. The result is extended to sets of
hamiltonian paths and sets of cycles that avoid a family of subgraphs.
In Chapter 3 we investigate necessary conditions for a hamiltonian graph to
contain cycles of all lengths, as well as determine what cycle lengths must be
present under a given set of conditions. We begin with a degree sum condtion
on two vertices of a hamiltonian cycle, using a result of Hakimi and Schmeichel
([13]) as a starting point. We then give analogous results for bipartite graphs,
though these results lack sharpness.
1.2 Background
1
We begin with some fundamental terminology and notation related to graphs
in general. We also include notation specific to the sections that follow. We
suggest [8] or [29] as a general resource.
A graph G = (V, E) is a finite set of nonempty objects called vertices together
with a set of unordered pairs of distint vertices of G called edges. The vertex
set of G is denoted by V(G) and the edge set by E(G). For a graph G with
u, v G V{G), the edge e = {u, v} is said to join u and v and we refer to u and v
as being adjacent. We will denote an edge e = {u, v} by uv. A graph defined in
this way is called a simple graph, since there is at most one edge between any
pair of vertices and a vertex is not adjacent to itself.
The order of a graph G is the cardinality of its vertex set, denoted  W(G) ,
and the size of G is the cardinality of its edge set, denoted .E((j). For a vertex
v G V{G), the degree of v, doin'), is the number of edges incident with v and
the neighbourhood of v, Nc(v), is the set of vertices adjacent to v. When the
context is clear, the subscript G is omitted. Let 6(G) and A(G) denote the
minimum degree and maximum degree of G, respectively. A graph in which
every vertex has degree r is referred to as an rregular graph.
For a a graph G (V, E) and a set S C V we define the induced subgraph
(TfS1] to be the graph with vertex set S and edge set T = {ee G Eande G S}.
That is, the edges of an induced subgraph include all edges of G that join vertices
in S. A subgraph of a G is a graph H = (S, T) where both S C V and T C E
and the assignment of endpoints to edges in G' is the same as in G. Note that
any subgraph of G is contained in an induced subgraph of G. If if is a subgraph
of G we write H C G. In Figure 1.1 we show an example of a simple graph along
2
a
.
b*
c*
Figure 1.1: A graph and two subgraphs.
with two subgraphs. The subgraph on the left is induced, whereas the subgraph
on the right is not, as it does not contain the edge cf. The complement G of a
simple graph G is the simple graph with vertex set V(G) defined by uv Â£ E(G)
if and only if uv Â£ E(G).
The disjoint union of graphs Gi,..., Gk is the graph G with V(G) = F(Gi)U
...UV (Gk) and E(G) E(G{) U ... U E(Gk) In the case where Gi = H for
all 1 < i < k, we write G = kH. The join of graph G\ and G2 is the graph
G = G1 + G2 with V(G) = V(G{)GV(G2) and E(G) = E(Gl)UE(G2)U{xy\x e
V(G1), y Â£ V(G2)}.
A clique in a graph G is a subgraph H C G in which every pair of vertices
of H are adjacent. If G itself is a clique, then we say that G is complete. The
complete graph on n vertices is denoted by Kn. An independent set in a graph
G is a set of pairwise nonadjacent vertices. A graph G is bipartite if V(G) is
the union of two disjoint independent sets called partite sets of G. A bipartite
graph G with parts X and Y is complete if for every x Â£ X, y Â£ Y, xy is an
3
edge of G. If the lr(X) = t and H(F) = n t. we denote G by Kt.nt
A path in a graph G is a sequence of distinct vertices ngG .. vk such that
vtvl+i is an edge of G for each i. 1 < i < k. If, in addition, ryiy is an edge of
G, then the sequence is a cycle. The order of a path or cycle is the number of
vertices in the sequence and the length is the number of edges contained in the
path or cycle. Thus a path of length k has order k + 1 while a cycle of length
k has order k. The distance between two vertices u.v Â£ V (G) is the length
of the shortest path connecting u and v and is denoted by dc(u,v). A graph
G is connected if every pair of vertices in G belongs to a common path; G is
disconnected otherwise.
Of particular interest is a path or cycle containing all the vertices of G. Such
a spanning path or cycle is called a hamiltonian path or cycle. If a graph G con
tains a hamiltonian path, we say it is traceable, and if it contains a hamiltonian
cycle, we say that G is hamiltonian. Hamiltonian graphs have been widely stud
ied, and a good reference for the recent status of such problems is [22], Let
(72(G) denote the minimum degree sum over all pairs of nonadjacent vertices
in G. Ores Theorem [20], one of the classic results pertaining to hamiltonian
graphs, states the following.
Theorem 1.1 (Ore 1960) If G is a graph of order n > 3 with a2(G) > n then
G is hamiltonian.
The requirement that <72 (G) > n is known as the Ore condition and we will refer
to similar degree sum restrictions as Oretype conditions.
4
Figure 1.2: Nonhamiltonian graphs with a2 n 1
A graph is a butterfly if it is composed of two complete graphs intersecting
in exactly one vertex. If G is isomorphic to a butterfly or if AWi n+i C G C
2 2
Kni + Kni, then G is nonhamiltonian and a2(G) n 1, demonstrating the
sharpness of Ores Theorem. In Figure 1.2 we show a butterfly of order n on the
left and Kni + Kn\ on the right, demonstrating that neither is hamiltonian.
2 2
In fact, it has been noted by several authors [1, 14, 18] that these are the only
nonhamiltonian graphs with this property. Diracs Theorem [9], another classic
result, is an immediate corollary of Theorem 1.1.
Theorem 1.2 (Dirac 1952) If G is a graph of order n > 3 with 5(G) > 
then G is hamiltonian.
We will refer to 5(G) >  as the Dirac condition.
Theorems 1.1 and 1.2 are the basis for much of the study related to cycles
in graphs. They led to the use of minimum degree and degree sum conditions as
determining factors for desired cycle structures. One such property introduced
by Chartrand is the idea of kordered. A graph is k ordered (hamiltonian)
if for every ordered sequence of k vertices there is a (hamiltonian) cycle that
encounters the vertices of the sequence in the given order. Ng and Schultz [19]
5
were the first to investigate such graphs.
Theorem 1.3 Let G be a graph of order n and let k be an interger with 3 <
k < n. Ifdeg(u) + deg(v) > n + 2k G for every pair u, v of nonadjacent vertices
of G, then G is kordered hamiltonian.
Corollary 1.4 Let G be a graph of order n and let k be an interger with 3 <
k < n. If deg(u) >  + k 3 for every vertex u of G, then G is kordered
hamiltonian.
Another property that is widely studied using minimum degree and degree
sum conditions is pancyclicity. A graph G of order n is pancyclic if it contains a
cycle of each length k for 3 < k < n. Bondy [6] showed that any graph satisfying
Ores condition is either pancyclic or isomorphic to ifis. Aldred, Holton and
Min [3] relaxed Ores condition and showed the following:
Theorem 1.5 If G satisfies 02(G) > n 1, then G is pancyclic unless G is
isomorphic to one of the following graphs:
1. a graph of order n consisting of two complete graphs joined at a vertex,
2. a subgraph of the join of a complete graph of order and an empty graph
of order
3. Kbl n, or
4 G5.
Given conditions that assure a graph contains a hamiltonian cycle leads to
the question: When does a graph contain more than one hamiltonian cycle? A
6
classic result of Smith (presented by Tuttc [28]) states that every edge of a 3
regular graph is contained in an even number of hamiltonian cycles. Thomason
[25] extended Smiths result to all rregular graphs where r is odd, and in fact
to all graphs in which all vertices have odd degree. Thomassen [26] completed
regular graphs for sufficiently large r.
Theorem 1.6 If G is hamiltonian and rregular with r > 300. then G has a
second hamiltonian cycle.
Thomassen also considered the question for bipartite graphs.
Theorem 1.7 ([27]) Let C = X\yiX2ij2 xnynx\ be a hamiltonian cycle in a
bipartite graph G.
1. If all the vertices yi,y2, ,yn have degree at least 3, then G has another
hamiltonian cycle containing the edge X\y\.
2. If all the vertices yi, y2,..., yn have degree d > 3 and if Pi, P2,..., Pq
(3 < q < d 3) are paths in C of length 2 of the form yi_iXiyi, then G
has at least 2q+1~~d(d q)! hamiltonian cycles containing Pi U ... U Pq.
Another natural direction is to question when a graph has multiple edge
disjoint hamiltonian cycles. Faudree, Rousseau and Schelp [11] gave an Ore
type condition for the existence of such hamiltonian cycles.
Theorem 1.8 Let k be a positive integer.
1. If G is a graph of order n > 60k2 such that 02(G) > n + 2k 2, then G
contains k edge disjoint hamiltonian cycles.
7
/
n 1
\
2. If G is a graph of order n > 6k and size at least
+ 2k, the G
contains k edge disjoint hamiltonian cycles.
Egawa [10] combined a minimum degree condition with a degree sum con
dition to prove the following result on edge disjoint hamiltonian cycles.
Theorem 1.9 Let n, k > 2 be integers with n > 44(k 1). If G is a graph of
order n with (72(G) > n and 6(G) >4k 2, then G contains k edge disjoint
hamiltonian cycles.
In considering conditions that guarantee a graph is pancyclic, the degree
bounds can be reduced if hamiltonicity is assumed. In 1981 Amar, Flandrin,
Fournier, and Germa [4] showed the following:
Theorem 1.10 Let G be a hamiltonian, nonbipartite graph of order n > 162.
If 6 > then G is pancyclic.
Hakimi and Schmeichel [13] showed that edge density could be reduced by
considering a pair of consecutive vertices on a hamiltonian cycle, which was a
variation of the bipartite results of Schmeichel and Mitchem [16].
Our focus will be the use of degree sum or Oretype conditions on hamil
tonian graphs. We will consider a cycle C in a clockwise direction and will use
C+ to represent that we are following the vertices in the cycle in a clockwise
direction and C~ to represent that we are following the vertices in the cycle in a
counterclockwise direction. Similarly, for a vertex Xi of the cycle, we represent
the vertex succeeding Xi on C as xf and the vertex preceding xl as x~. For
8
a set of vertices S of a graph, we use NC(S) to denote the set of neighbours
of elements of S on C, N+(S) and N~(S) to represent the vertices on C that
succeed and precede neighbours of S, resectively.
9
2. Favoiding Hamiltonian Graphs
As noted in the previous chapter, the idea of imposing structure on a hamil
tonian cycle has been considered, as is evidenced by ^ordering. In [15], Kronk
extended a theorem of Posa [21], giving a condition under which certain edges
were contained in a hamiltonian cycle. Aldred, Holton, Porteous, and Plummer
[2] considered matchings that contained certain edges while avoiding others. We
are interested in a hamiltonian cycle in a graph G that avoids sets of edges.
2.1 FA voiding Hamiltonian
Let G be a graph and H be a subgraph of G. If G contains a hamiltonian
cycle C such that E(C) Pi E(H) is empty, then we say that C is an Havoiding
hamiltonian cycle. Let F be any graph. If G contains an Favoiding hamiltonian
cycle for every subgraph H of G such that H = F, then we say that G is F
avoiding hamiltonian. We note here that G is Favoiding hamiltonian if and
only if G E{H) is hamiltonian for every subgraph H of G such that H = F.
We wish to determine conditions on G and F that assure that G is Favoiding
hamiltonian.
The closure of a graph G of order n, denoted cl(G), is obtained by recursively
joining nonadjacent vertices u and v whenever d(u) + d(v) > n until no such
pair of vertices exists. The following theorem from [7] will be used several times
in this section.
Theorem 2.1 A graph G is hamiltonian if and only if cl(G) is hamiltonian.
We first give two Oretype conditions that assure G is Favoiding hamiltonian.
10
Theorem 2.2 Let G be a graph of order n > 3 and let F be a graph of order
t <  and maximum degree at most k. If a2(G) > n + k then G is Favoiding
hamiltonian. This result is sharp for all choices of F.
Proof: Let H be any subgraph of G that is isomorphic to F and let
G' = G E(H). It suffices to show that G' is hamiltonian. We will, in fact,
show that d(Gr) is hamiltonian implying the result by Theorem 2.1. Let v be
an} vertex in G' that is not a vertex of H and let w be any vertex in G' that is
not adjacent to v. Then defw) > dc(w) k and dc(v) = dc(v), so that
dc'{v) + dc{w) > dc{v) + dc{w) k > (n + k) k = n.
This implies that v and w are adjacent in d(G') and, in fact, dcgG')(v) = n 1.
Since t < , this implies that at least  vertices have degree n 1 in the closure,
and hence all vertices of cl{G') have degree n 1. Consequently, cl{G') Knj
which is hamiltonian implying by Theorem 2.1, that G' is hamiltonian as well.
The result follows.
Let H be any graph with A(H) < k and let x be a vertex of maximum degree
in H. To see that the theorem is sharp, consider a the graph G on n vertices
constructed from iLn_i and an additional vertex v of degree A(H) + 1, shown
on the left of Figure 2.1. This graph has a2 < n + k 1 since A(H) < k and
contains numerous copies of H with v playing the role of x. Removing the edges
of any of these copies from G leaves a graph that is clearly not hamiltonian, as
the degree of v would be one, as is shown on the right in Figure 2.1.
In Theorem 2.2, note that in order to assure the existence of a hamiltonian
cycle that avoids any nonempty collection of edges in G, we must exceed the
11
Figure 2.1: A graph G with a2(G) < n + k 1 that is not //avoiding
harniltonian.
Ore condition. Perhaps unexpectedly, this is not so when we consider the Dirac
condition.
Theorem 2.3 Let G be a graph of order n > 3 with 5(G) > f If E1 is any
subset of E(G) such that \E'\ < n~ then there is a harniltonian cycle in G
containing no edge from E'. This result is sharp.
Proof: It suffices to prove the theorem when \E'\ = Let H be the
subgraph of G induced by E'. Note that H has at most vertices. For
convenience let G' be G E'. We proceed by considering cl(G'). Each vertex in
G V(H) still has degree at least  in G', and as such the graph on V(G) V(H)
is complete in cl(G'). Let v Â£ V(H) be a vertex of degree A(H). Then
77 fl
\V(H)\ < A(H) + 1 + 2(F/ A(H)) < A(H) + 1,
as F(//) would be maximized in the case where those edges not adjacent to
v form a matching in H. This implies that \V(G) V(H)\ = n \V(H)\ >
+ A(H) 1. Thus, since G V(H) induces a clique in cl(G') each vertex in
G V(H) has degree at least Ap + A(H) 2. We now also note that each vertex
in V(H) has degree at least ~ A(H) in G'. Let x and w be arbitrary vertices
in G' chosen from V(H) and G V(H) respectively. After closing G V(H),
12
we have that
d(x) + d(w) > Q A(//)j + ^ (' + A(H) 2^ = n + 1 > n.
This implies that for any choice of x and w, xw is in cl(G'). Consequently,
cl(G') contains the join of K\gv(H)\ and K\v(h)\, which is hamiltonian since G
V(H)  > \V(H). Thus, as d{G') is hamiltonian, G is //avoiding hamiltonian.
and the result follows.
To see that the theorem is sharp, let k > 2 be a positive integer, and let
n = 4k + 2. We construct a graph H of order n by starting with the complete
bipartite graph Kn_l^+1 and adding the matching ei,...,e^+i to the partite
set of size  + 1. Removing any k = of the edges e* yields a nonhamiltonian
graph. Thus, if G is /^'avoiding hamiltonian, \E'\ < ^ 1 =
We now turn our attention to the problem of finding Favoiding hamiltonian
cycles in a graph G when the order of F is closer to the order of G. The next
result can be obtained using techniques like those in the proof of Theorem 2.2,
and is also a corollary of the theorem that follows, so here we provide only the
sharpness example.
Theorem 2.4 Let G be a graph of order n > 3 and let F be a graph with
maximum degree k. If 02(G) > n + 2k then G is Favoiding hamiltonian. This
result is sharp for all values of k.
To see that the theorem is sharp for every value of k, let n > 2k + 1 be
an odd integer and let B be any fcregular bipartite graph with partite sets of
size In each partite set of B add an edge between every pair of vertices
so that each partite set is a copy of Kn=i, forming a (no longer biparite) graph
13
D'. We then create the graph G by taking the join of D' and Ai and we note
that 02(G) = // + 2k 1. If we remove the edges of the bipartite graph B.
we are left with two cliques of order intersecting in a vertex, which is not
hamiltonian. This implies that G is not ^avoiding harniltonian, establishing
the desired sharpness.
If we relax the degree condition in Theorem 2.4 slightly, it becomes possible
that G E(H) is no longer hamiltonian. We can show however, that if G E(H)
is not hamiltonian then it must fall into one of two exceptional classes.
Theorem 2.5 Let k > 0 be an integer and let G be a graph on n > 2k + 3
vertices ivith 02(G) > n + 2k 1. If F is a graph with maximum degree at most
k, then G is Favoiding hamiltonian, or there is some subgraph H of G such that
H = F and either G E(H) is a butterfly, or Kn=\ n+i C G C Kn1 + Kn+1.
Before we begin we will give some useful notation and lemmas. Define G' to
be the graph G E(H) and observe that 02(G) > n + 2k 1 implies that the
minimum degree of G is at least 2k + 1 and hence that the minimum degree of
G' is at least k+1. Moreover, for any vertices x, y G V(G) such that xy is not
an edge in G, dc'{x) + defy) > n 1.
The following two lemmas will be used to prove Theorem 2.5.
Lemma 2.6 Let G be a graph onn>2k + 3 vertices with a2(G) > n + 2k 1.
Then for any subgraph H C G with A(H) < k, either G' is a butterfly or G' is
2connected.
Proof: Let H be a subgraph of G with A(H) < k. We will show by way
of contradiction that G' is a butterfly or is 2connected.
14
Suppose that G' contains a vertex v such that G' v is disconnected, and
let Si and Sj be two components of G1 v with Vr(S)) = Si and l/(S'j) = Sj.
Since the minimum degree of G' is at least k + 1, the minimum degree of G' v
is at least k. Hence each component of G' v has at least k + 1 vertices. Let
r be a vertex in St. Then for all j / i, there exists y Â£ Sj such that xy is
not an edge in G, and therefore dc{x) + do>(y) > n 1. (Note that this is
true for every vertex of G' v.) We also have that dc(x) < s, and defy) < Sj.
Combining the inequalities we get n 1 < dc> (x) + dc> (y) < Si + Sj < n 1, which
implies that s* + Sj = n 1 (and also that G' v has exactly two components),
dc'{x) = Si dc(y) = Sj and both x and y are adjacent v. This is true for all
x Â£ V(Si), y Â£ V(Sj), so G' is a butterfly.
Lemma 2.7 Let G be a graph on n > 2k + 3 vertices with a2{G) > n + 2k 1
and let H be any subgraph of G with A(H) < k. Let C be a longest cycle in G',
with \C\ = t. For any component S of G' C with [ AGv(S) I A 2 we have the
following:
1. For all x Â£ V(
E{G'). (For all x Â£ V(S) and for all xi}xj Â£ Nc(S) xfxj Â£ E{G') and
xfx ^ E{G').) Furthermore, 7VC>(5') <
2. For all x Â£ V(S) and for all ay Â£ Nc(S) such that xxf E(G), and for
all y i Nq{S) U V{S), xfy Â£ E(G'). (For all x Â£ V{S) and xz Â£ NC{S)
such that xxf Â£ E(G), and for all y Â£ Nf,(S) U V(S), xfy Â£ E(G').)
Furthermore, x is adjacent to every vertex ofV(S) x.
15
Figure 2.2: Extending a cycle C to a longer cycle.
Proof: Let G, H and C satisfy the hypothesis. For convenience let
/Vc(5') = Â£ and note that we are considering NG(S) in the graph G'.
To show 1 let x G V(S) and xi,xj Nc(S). Then xxf is not an edge of G'
since XiXxf C+Xi would be a longer cycle in G1, as is seen on the left in Figure
2.2. Suppose that xfx^ is an edge in G'. Then xXiC~x^xf C+XjX would be a
longer cycle in G', as is seen on the right in Figure 2.2. The argument for xj
and xj is similar.
To show 2 let x e V(S) and xt NC(S) such that xx* .is neither an edge
in G' nor G. Then we know that dGi (x) + dc{x j ) > n 1. Since there are no
edges between components of G' C, do'(x) < IFfS1)! 1 + t. Recall from
(2) that xf is not adjacent to any vertex of Nq(S) nor V(S), so do'{xf) <
t Â£ + n t \V(S)\ = n F(S) Â£. Combining the inequalities yields
n 1 < dG'{x) + dG>{xt) < n 1. Therefore equality must hold, so x must be
adjacent to every vertex in V(S) x and xf must be adjacent to every vertex
in G' Nq(S) V(S). The argument for xj is similar.
We are now ready to prove Theorem 2.5.
16
Proof: Let G be a graph on n > 2k + 3 vertices with a2(G) > n + 2k 1
and let H be any subgraph of G with A(H) < k. Let C be a longest cycle in
G' and let t = \ V(C)\. If C is a harniltonian cycle, we are done. Suppose then
that C is not a harniltonian cycle.
We begin by showing that G' C is connected. Suppose otherwise and
let Si,... ,Sh be the components of G' C. with V'(5j)j = s, for 1 < i < h.
Without loss of generality we will assume that s, < .sl+i for 1 < i < h 1.
Let x e Si and y e Sj for some distinct i and j. Then by part (1) of
Lemma 2.7, dc{x) < Sj 1 +  and dc(y) < Sj 1 +  which implies that
dG'(x) +dG'(y) < st + Sj + t 2 < n 2 and hence dG(x) + dG(y)
Consequently, as x and y are nonadjacent in G', xy must be an edge in H. Since
x and y are arbitrary vertices of any two distinct components, this is true for
every pair of vertices in different components of G' C. At most k edges of H
were incident with each vertex in each Si, so Si < k for all 1 < i < h.
Assume without loss of generality that x E Si and consider the neighborhood
of x on C. In G
dG(x) > 2k + 1 (sj 1) Sj > 2k + 2 hsh
Since at most k edges of H were incident with each vertex in G, at most (L l).sy
edges between St and Sj are in H for all j ^ i, so in G'
dG(x) > 2k + 2 hsh (k (h 1 )s/l) = k + 2 Sh
At most k Sh of the nonneighbors of x on C in G' were neighbors of x on
C in G. Therefore, there exist xiyXj 6 NG{x) such that xx\,xxk is neither an
edge in G' nor G. By part (2) of Lemma 2.7 both ay+ and xj~ are adjacent to
17
every vertex of G' not in /f(t(.r)uV,(.5'i). Recall that y G Sj, where j / 1. Then
the cycle xX{C~xjy:if C+XjX is longer than C. which contradicts that C is a
longest cycle of G'. Therefore, G' C is connected.
Let S be the graph G' C and define the neighborhood of S in C to be
NC{S). Suppose that Arc(S') = L Note that if G' is not 2connected, then by
Lemma 2.6 G' is a butterfly. We will assume that G' is 2connected.
Suppose that the order of S is at least k+ 1 and let xt be in NG(S). Since S
is connected, no vertex in S can be adjacent to xf. but at most k edges incident
with ay+ were in H. Consequently, as there are at least k + 1 vertices in S, there
exists v G V(S) such that xfv is neither an edge in G' nor G, which implies
dGi(xf) + do'{v) > n 1. Then by part (2) of Lemma 2.7 we know that for
every ay G NC{S), NG>(xf) = V(C) NÂ£(S). This means that dc(xf) t Â£
for all Xi G Nc(S). Since dG'{v) < IRIS')! 1 + Â£ n t l+Â£, we also have
that dG'(xf) + dGi(v) < n 1, so equality must hold. Consequently v must be
adjacent to every vertex in NG(S) and V(S) v.
Suppose there is Xj G NG(S) such that its predecessor x~ is not in N^(S);
that is, there are at least two consecutive vertices on the cycle that are not in
the neighbourhood of S. We have shown above that xjxj and xj~_1Xj G E(G).
Then the cycle vXj_iC~Xj'xjC~x^_1XjV has length t + 1, which contradicts
that C is a longest cycle of G'. So for each xJ; (xj)~ is in NG(S), implying
that iVc(S') = . Since G' is 2connected, there exists u G V(S) with u ^ v
and Xi G NC(S) such that uxi G E{G'). Then the cycle vXi_iC~XiUV has
length t+ 1, which contradicts that C is a longest cycle of G'. Therefore, we
will assume that S has order at most k. Suppose then that j W(5")  = r, where
18
Figure 2.3: Extending a cycle C to a longer cycle.
2 < r < k. Since the minimum degree of G' is at least k + 1. every vertex in
S has at least k + 1 (r 1) = k r + 2 > 2 neighbors on C. Let u,v be
in V(S) and Xi,Xj be in Nc(S), such that uxi.vxj Â£ E(G'), and let P be any
u v path in S. For every vertex y Â£ V(C) such that x^y Â£ E(G') either
x~j~y~ ^ E(G) or x^y+ ^ E(G'). Indeed, if y were to lie between xj~ and xj
on C, the cycle uXiC~x^y^C~xfyC+XjvPu would be longer than C, as can
be seen in the left of Figure 2.3, and if y were to lie between xL and x~l on C
the cycle uxiC~y+xJC+yxf C+xjvPu would be longer than C, as can be seen
in the right of Figure 2.3. Thus t < n 2 implies that dcixf) f dcix^) =
dc(xf) + dc{x~j') < n 2 and therefore that xfxj Â£ E{G) for all xitXj Â£ NC(S).
Since xf x^ is not in E(G') for any x{, Xj Â£ NC(S), these edges must be in E(H).
But the minimum degree of G' is at least k + 1, so 1^(5) > k r + 2 implies
that there are at least k r + l such edges for each xf. Then r < k implies that
there is at least one vertex w Â£ V(S) for each xf such that vjxf is neither an
edge in G' nor G. (These w are not necessarily distinct.) By the same argument
used above we see that jAr(S')J = so we can find a cycle longer than C, which
19
is a contradiction.
Hence we may assume that jI/(S')j = 1. Let x be the vertex in S and suppose
that dc{x) < Then there is a vertex xj G A^(x) such that xxj is neither
an edge in G' nor G and a vertex xj G Nc (x) such that xx~ is neither an edge
in G' nor G. Then by part (b) of Lemma 2.7. xj is adjacent to every vertex
in V(C) NÂ£(x) and xj is adjacent to every vertex in V(C) Nj, (x) First
suppose that x,+ = xj+l', that is, xj is the only vertex between x, and x,+i on
C. Since dcfx) < there exists a vertex xsuch that x Nj{x). Then
the cycle xxlC~xmxjxflC~xi+ ix is hamiltonian, which contradicts that C is a
longest cycle in G'. So xj 7^ x~+l. By a similar argument we find that xj 7^ xj_j.
Hence by part (2) of Lemma 2.7 we know that xjxj and xjxj are edges in G'.
Then the cycle xXiC~ xj xj C~ xj XjX is a hamiltonian cycle, which contradicts
that C is a longest cycle in G'. Therefore we may assume that dc{x) =
Observe that Nj(x) U x is an independent set of order Since n > 2k + 3,
> k + 2, so for every vertex y G Nj(x) U x there is a vertex z G Nj(x)
such that yz is neither an edge in G' nor G. Then every vertex in Nj (x) U x is
adjacent to exactly Nc{x). It follows that Kn+1 ni CG'C Kni + Kni.
The conclusion that there is a subgraph H = F such that G E(H) either
falls into the class of butterflies or is a supergraph of Knin+i is only feasible
for certain choices of F. The following two corollaries reflect this.
Corollary 2.8 Let k > 0 be an integer and let G be a graph on n > 2k + 3
vertices with a2(G) > n + 2k 1. If F is a graph of order n with minimum
degree at least 1 and maximum degree at most k, then either G is Favoiding
hamiltonian or there is some subgraph H of G such that H = F and Kni n+1 C
20
G E(H) C Kn=i + Kn+i.
2 2
Corollary 2.9 Let k > 0 be an integer and let G be a graph on n > 2^ + 3
vertices with <72(G) > n + 2k 1. If F is a connected graph with maximum degree
at most k and order at least  + 1. then either G is Favoiding hamiltonian or
F is bipartite, has order at most n 1. and there is some subgraph H of G such
that H = F and G E(H) is a butterfly.
The problem of determining when a graph contains k edgedisjoint, hamil
tonian cycles has long been of interest. In [11], it was shown that a graph G
of sufficiently large order n with a2(G) > n + 2k 2 contains k edgedisjoint
hamiltonian cycles. The problem of finding disjoint hamiltonian cycles in bi
partite graphs has also been examined [12], Other results focus on finding k
edgedisjoint hamiltonian cycles in graphs that satisfy the Ore condition. In
[10], it is shown that if G is a graph of sufficiently large order n with <72(G) > n
and 5(G) > 4k 2 then G contains k edgedisjoint hamiltonian cycles.
In light of these results, we present the following variation. Let H be a
family of k > 1 edgedisjoint hamiltonian cycles in a graph G. If G E(H)
is hamiltonian, then G E(H) contains a hamiltonian cycle C which, together
with H, would comprise a family of k + 1 edgedisjoint hamiltonian cycles in G.
In fact, if G is Favoiding hamiltonian for graph F isomorphic to k edgedisjoint
hamiltonian cycles, then we are not only finding disjoint families of hamiltonian
cycles, but in fact we are able to extend any family of k edgedisjoint hamiltonian
cycles to a family of k + 1 edgedisjoint hamiltonian cycles. Taking into account
Corollaries 2.8 and 2.9, the following is an immediate consequence of Theorem
21
2.5.
Corollary 2.10 Let k > 0 be an integer and let G be a graph, on n > 4k + 3
vertices with a2(G) > n + 4k 1 and let H be any collection of k edgedisjoint
hamiltonian cycles in G. Then H can be extended to a family of k + 1 edge
disjoint hamiltonian cycles. This result is sharp.
Corollary 2.10 complements the results mentioned above pertaining to the
existence of k edgedisjoint hamiltonian cycles. To see that Corollary 2.10 is
sharp, consider a graph G of even order n > 4k + 4 which is comprised of two
disjoint cliques of order , denoted Gi and G2, and a family H of k edgedisjoint
hamiltonian cycles with the property that H is bipartite with partite sets V{G\)
and V(G2). Then a2(G) = n + 4k 2, but G E(H) is isomorphic to 2/C
which is not hamiltonian.
Since a hamiltonian cycle of even order can be viewed as the union of two
disjoint perfect matchings, we also obtain the following result pertaining to
extending families of perfect matchings.
Corollary 2.11 Let k > 0 be an integer and let G be a graph of even order
n > 2k + 3 with a2(G) > n + 2k 1 and let H be any collection of k edge
disjoint perfect matchings in G. Then H can be extended to a family of k + 2
edgedisjoint perfect matchings in G. This result is sharp.
To see that Corollary 2.11 is sharp, let t be an odd integer such that 21 >
2k 1. Consider a graph G of order 21 which is comprised of two disjoint
cliques of order t, denoted G\ and G2l and a family H of k edgedisjoint perfect
matchings with the property that H is bipartite with partite sets V(Gi) and
22
F(G2). Then
does not contain a perfect matching as t is odd.
As mentioned above, certain supergraphs of Kn^i n+i and the class of but
2 2
terflies serve to establish the sharpness of Ore's Theorem. That is, they are
examples of nonhamiltonian graphs of with cr2 = n 1. If we let k = 0 in The
orem 2.5 we can see that these are in fact the only such graphs. As mentioned
above, this fact was also noted in [I], [14] and [18].
Corollary 2.12 Let G be a nonhamiltonian graph of order n with cr2(n) = n 1.
Then either G is a butterfly or Kn^i n+i C G C Kn^i + Fn+i.
A graph G is traceable if it contains a spanning path, that is, a path
containing every vertex of G. Such a path is known as a hamiltonian path.
We say that G is Favoiding traceable if for any subgraph H of G such that
H = F, G E(H) has a hamiltonian path. The following is an immediate corol
lary of Theorem 2.5, as hamiltonian graph, butterflies and graphs G satisfying
Kni n+i CGC Kn1 + Kn+i are traceable.
2 2 2 2
Corollary 2.13 Let k > 0 be an integer and let G be a graph on n > 2k + 3
vertices with n + 2k 1. If F is a graph with maximum degree at most
k, then G is Favoiding traceable.
2.2 Favoiding Pancyclicity
A graph G is pancyclic if G contains a cycle of each length from 3 up to
P(G). The study of pancyclic graphs is a natural extension of the hamiltonian
problem. Having developed necessary conditions for a graph G to be Favoiding
23
Hamiltonian, we turn our attention to the analogous notion for pancyclic graphs.
Let F and G be graphs. If G E(H) is pancyclic for every subgraph H of G
such that H = F. then we say that G is Favoiding pancyclic. In this section
we will present several conditions on G and F which assure that G is Favoiding
pancyclic. In addition to Theorem 2.5, the following two theorems from [13] will
be useful.
Theorem 2.14 Let G be a graph of order n with V(G) = {to.... ,un_i} and
harniltonian cycle Vo,... ,vni,vo. If d(vo) + d(un_i) > n then G is either pan
cyclic. bipartite or missing only an (n l)cycle.
Theorem 2.15 Let G be a graph of order n with V(G) = {u0,... ,nn_i} and
harniltonian cycle v0,..., un_i, v0. If d(v0) +d(vni) > n +1 then G is pancyclic.
We begin with an oretype condition for //avoiding pancyclicity that leaves
us with no exception graphs.
Theorem 2.16 Let G be a graph of order n and let F be a graph with maximum
degree k. If n + 2k + 1 then G is Favoiding pancyclic. This result is
sharp for all values of k.
Proof: By Theorem 2.4 we know that G' = G E(F) is harniltonian.
Let x be a vertex of G with d(x) = S(G). Then there is a vertex y of G
with d(y) > n + 2k + 1 5(G). Let C be a harniltonian cycle in G'. Then
dG'(y) + dG'(y+) >n + k + 1 5(G) + 5(G) k = n + 1, so G' is pancyclic by
Theorem 2.15.
24
To see that this result is best possible, let n > 2k + 2 be an even integer and
let II be any /..regular graph on  vertices. We create the graph G by taking
the join of two copies of H. Then (12(G) = n + 2k: and the removal of the edges
of each copy of H leaves us with AT s, which is not pancyclic since it contains
no odd cycles.
The following is a wellknown result of Bond}' [Gj.
Theorem 2.17 Let G be a graph of order n > 3. If a2(G) > n then either G
is pancyclic or G is isomorphic to K
If we relax the conditions on
a similar result.
Theorem 2.18 Let k > 0 be an integer and let G be a graph on n > 6k + 4
vertices with a2(G) > n + 2k. If F is a graph with maximum degree at most
k, then G is Favoiding pancyclic or there is some subgraph H of G such that
H = F and G E(H) is A^n. This result is sharp for all values of k.
Proof: For simplicity we let G' = G E(H). By Theorem 2.4 we know
that G' contains a hamiltonian cycle C. If n the result follows by
Theorem 2.17. Suppose that cr2(G') < n and that G' is not pancyclic. Let v be
a vertex with degree 6(G') < Then, as n + 2k and dH(v) < k there
are at least ^ k vertices of degree at least n S(G') > Since n > 6fc + 4,
k > and we can find two vertices x and y on C such that both x and
y have degree at least Tjd and 1 < dc(x, y) < 2.
If dc(x,y) = 1 then G' is pancyclic by Theorem 2.15. Therefore we may
assume that dc(x,y) = 2.
25
We assume without loss of generality that x = y++ on C and for convenience
let C = v0, ii.... vi, Vo with x = v0 and y = By Theorem 2.14. since
dc>{x) + dGi(vn_i) > (n 5(G')) + S(G/) = n, we need only show that G' contains
an (n l)cycle. In G" = G' vn\, consider the hamiltonian path vq, ..., wn2
We have dG"(v0) + dG(vn2) > n + 1 2 = n 1, hence G is hamiltonian and
therefore G contains an n 1cycle. The result follows.
To see that the result is sharp, let n = 3(mod 4) and let H be any k
regular graph on Tp1 vertices. If we let G denote the join of H and Kn^i then
<72(G) = n + 2k 1 but G E(H) is isomorphic to AGi +i.
26
3. Cycles in Hamiltonian Graphs
In this chapter we will investigate the existence of cycles of various lengths
in hamiltonian graphs. In the same paper in which Bondy proved Theorem 2.17
he stated the following metacoiijecture:
Conjecture 3.1 (Bondys Metaconjecture) Almost any nontrivial condi
tion on a graph which implies that the graph is hamiltonian also implies that
the graph is pancyclic. There may be a simple family of exceptional graphs.
In light of Conjecture 3.1, it has been of interest to examine the relation
ship between hamiltonicity and pancyclicity in graphs. Schmeichel and Mitchem
suggested that degree bounds in theorems guaranteeing pancyclicity could be
reduced if hamiltonicity were assumed. Ores Theorem and Theorem 2.17 both
consider graphs where 02 is high enough to assure a considerable amount of
global density. We wish to relax the Ore condition and examine the cycle struc
ture of hamiltonian graphs that may be globally sparse yet have a small number
of vertices with higher degree. Schmeichel and Mitchem proved Theorems 2.14
and 2.15, in which edge density is greatly reduced. These theorems serve to
motivate our investigation, as they require only a single pair of vertices having
high degree sum. However this pair of vertices must be consecutive on some
hamiltonian cycle in G. Our goal is to extend Theorems 2.14 and 2.15 by exam
ining hamiltonian graphs containing a pair of vertices that have a high degree
sum but may lie far apart on every hamiltonian cycle.
3.1 Absolute Bounds
27
We begin by determining the degree sum of two vertices on a hamiltonian cy
cle, regardless of their placement, required to assure that the graph is pancyclic.
We start with the following two useful lemmas.
Lemma 3.2 Let G be a hamiltonian graph of order n > 5 with hamiltonian
cycle C. If there exists a vertex x in V(G) of degree n 2, then G is pancyclic.
Proof: Let C = xv\ . i'niX and let vt, for some 2 < i < n 2, be the
vertex nonadjacent to x. If xiy is an edge of G, then the cycle C' = xveC~x is
a cycle of length Â£ + 1 in G, so our assumption implies that G contains cycles
of all lengths except possibly a cycle of length (i + 1). However, since n > 5,
there exist vertices v3 and vJ+l_i in G that are both adjacent to x, and hence
xVjC+Vj+i_\X is an (i + 1)cycle. Consequently, G is pancyclic.
Lemma 3.3 Let G be a hamiltonian graph of order n > 7 with hamiltonian
cycle C. If there exists a vertex x in V{G) of degree n 3, then either G is
pancyclic or G contains a cycle of each length except (n 1).
Proof: Let C = xv\... vn_ix and let Vi,Vj, 2 < i < j < n 2, be the
vertices of G that are not adjacent to x. As above, we may conclude that G
contains cycles of all lengths except possibly cycles of length (i + 1) and (j + 1).
If i = 2 and j = n 2 then G contains cycles of each length except possibly
n 1. For all other i. j, since n > 7, there exist distinct vertices Xk and Xf
such that Xk, xjt+ii, xe+ji are all adjacent to x. Then xxkC+Xk+iix is
an (i + l)cycle in G and xxf:C+xi+]^iX is a (j + l)cycle in G, implying that G
is pancyclic.
28
When considering a Hamiltonian graph with two vertices of high degree sum.
placing no restrictions on their proximity on a Hamiltonian cycle, the sum that
guarantees the graph is pancvclic turns out to be quite large.
Theorem 3.4 Let G be a Hamiltonian graph of order n > 9. If there exist
x.y Â£ V(G) such that d(x) + d(y) >2n 7, then G is pancyclic. This result is
sharp.
Proof: Assume that G is not pancyclic, and let C ryqi vni An where
x = t'o, be a hamiltonian cycle in G. Since d(x) + d(y) > 2n 7, we may
assume without loss of generality that d(x) is at least n 3. Lemmas 3.2 and
3.3 therefore imply that x has degree exactly n 3 and furthermore, since by
assumption G is not pancyclic, that G contains cycles of each length except
n 1. As such, we can see that v2 and un_2 must be the vertices of G that
are not adjacent to x. We now consider the vertex y, which has degree at least
n 4.
It is useful to note that if y was either vn\ or tq, this would place x and
y consecutive on a hamiltonian cycle, implying that G would be pancyclic by
Theorem 2.15. Thus, we assume y is neither vn\ nor tq. We also note that y
has at most three nonadjacencies, and two of these must be y and y++ since
G does not contain a cycle of length n 1.
Suppose then that y v2,v3 or v4. Then either yvn^i or yvn2 is an edge
of G. If yvn^i is an edge of G, then yvn_iC~y++xC+y is an (n l)cycle in
G, and if yvn_2 is an edge of G, then yvn^2C~y+xC+y is an (n l)cycle in G.
Similarly, if y = u_4, un_3 or un_2 then either yvx or yv2 is an edge of G. If ytq
29
is an edge of G. then yvlC+y~~xC~y is an (n l)cycle in G and if yv2 is an
edge of G, then yv2C+y~xC~ y is an (n 1)cycle in G.
If y ^ v2. i'314t'n4, tn3: vn2; then at least one of yvn_\ and yiy is an edge
of G, impling that one of the following is an (n l)cycle in G:
yC+xy C~i\y,
or
yC~xy++C+vniy.
Having exhausted all cases, we may conclude that G is pancyclic.
To see that this result is sharp, consider the graphs G\ and G2 constructed
as follows:
Let V(G\) = {t>o5 rVii} and construct the hamiltonian cycle C =
VqV\ ... n_iu0 in G\. Selecting x = v0 and y = un_3 we let xvi be an edge
for each i ^ 0, 2, n 5, n 2 and yvj be an edge for each j yt 2, n 5, n 3, n 1.
Then d(x) + d(y) = 2n 8, but G\ contains no (n l)cycle. See Figure 3.1.
Let V(G2) {v0,.. ,vni} and construct the hamiltonian cycle C =
v0vi... nn\VQ in G\. Selecting x v0 and y we let xvt be an edge
for each i ^ 0,2,n 6,n 2 and yvj be an edge for each j 7^ 2, n 6, n 4, n 2.
Then d(x) + d(y) = 2n 8, but G2 contains no (n l)cycle. See Figure 3.2
In both G\ and G2, the distance between x and y on the hamiltonian cycle
C is at most four. If we require that this distance be at least five, the necessary
degree sum for pancyclicity can be reduced slightly.
Theorem 3.5 Let G be a graph of order n > 9 with hamiltonian cycle C. If
there exist x, y Â£ V(G) such that distc(x, y) > 5 and d(x) + d(y) > 2n 9, then
30
Figure 3.1: d(x) + d(y) = 2n 8, but G contains no (n l)cycle
Figure 3.2: d{x) + d(y) = 2n 8, but G contains no (n l)cycle
31
G is pancyclie. This result is best possible.
Proof: Assume that G is not pancyclie, and let C xvi... vn\X. Since
d(x) + d(y) > 2?> 9, we may assume without loss of generality that x has
degree at least n 4. By Lemmas 3.2 and 3.3 and the assumption that G is not
pancyclie, we may assume that x has degree at most n 3.
Suppose that the degree of x is exactly n 3 and therefore, by Lemma 3.3.
G contains cycles of each length except n 1. Then we can see that v2 and vn2
are the vertices of G that are not adjacent to x. We now consider the vertex y,
which has degree at least n 6.
Since distc(x, y) > 5 we know that y ^ i'n3, un_2, Wi, An ^i, Ln Ln t>4}.
If at least one of yy or yy++ is an edge of G, then G contains an (n 1)
cycle and is pancyclie. so we assume that neither y nor y++ are adjacent to
y. If yvx e E{G) or 1 G E(G), then xy~C~viyC+x or xC+yvn\C~y++x
is an (n l)cycle, so we may also assume that yv 1, 1 ^ E(G). Since y can
have at most five nonadjacencies, one of yun_2 and yv2 is an edge of G, and G
contains the (n l)cycle xy+C+vn^2yC~x or xC~yv2C+y~x. Thus, if x has
degree exactly n 3, G is pancyclie.
Suppose, then, that x has degree n 4 and let vt, v3 and be the nonneigh
bors of x in G We know that for k 7^ i,j,Â£ G contains the k + 1 cycle xC+V}cx.
If i ^ n n j jL n Â£, and i,j,Â£ ^ then the cycle C' = xvnmC+x is a
cycle of length m + 1, where rn and G is pancyclie.
Without loss of generality, suppose then that i = If j, Â£ ^ 2, the
cycle xvi+i C~v2x has length i + 1. If j or Â£ = 2 or if j or i = then G
contains either the (i + l)cycle xui_1C'+u_2X or xui_2C'+uTl_3x. Now we must
32
find the cycles of lengths j + 1 and Â£ + 1. If j A n 1, G contains the (j + 1) and
(Â£ + l)cyeles C = xr,_mC'+x as above, where in = j. Â£. If j = n Â£ ^ 2, then
xvm+iC~v2x or xvn_m_}C+vnox is a cycle of length m + 1, where m = j,Â£. If
j = n Â£ = 2, we will find an (n l)cycle by using the vertex y. As above, we
know that y Â£ {r_4. r_3, v2, tniWo, O ,v2. v3. v4}. and that, yy~~, yy++, yvu
and yvni are not edges of G. Now. y can have at most four nonadjacencies, so
G contains the (n l)c.ycle xy+C+vn2yC~x.
Thus, we may assume without loss of generality that i = n j (and hence
i,j A n Â£). Observe that if Â£ A  the (Â£+ l)cycle C' = xvniC+x is contained
in G If Â£ =  an (Â£ + l)cycle can be found in G as described above. We
proceed by considering three cases.
Case 1: Assume i A 2, If Â£ A 2, i + 1, j + 1, then xvi+4C~v2x is an
(i + l)cycle and xVj+iC~v2x is a (j + l)cycle. If Â£ 2, i + 1, or j + 1, then
xvi+2C~v3x is an (i + l)cycle and xvj+2C~v3x is a (j + l)cycle.
Case 2: Assume i = and j If Â£ A 2, 3, j + 1, then xvi+2C~v3x is
a cycle of length i + 1 and xVj+\C~v2x is a cycle of length j + 1. If Â£ = 2,3, or
j + 1, then xVi^iC+vn^3x is a cycle of length i + 1 and xvj2C+vn2x is a cycle
of length j + 1.
Case 3: Assume i = 2 and j = n 2. As noted above, if at least one
of yy or yy++ is an edge of G, then G contains an (n l)cycle, so we will
assume that these edges are not in G.
If Â£ = y~, then if yvi, or yvn_2 Â£ E(G), the (n l)cycle xy C~v4yC+x or
xC+yvn^2C~y+x is contained in G. If yv4,yvn2 Â£ E(G), then yvn_i Â£ E(G),
and G contains the (n l)cycle xC+yvniC~y++x. If Â£ = y+, the argument is
33
Figure 3.3: d(.r) +d(y) = 2n 10, but the pictured graph contains no (n 1)
cycle
similar, so we assume that Â£ ^ y~ ,y+.
If yvi E E(G) or yvn^i E E(G), then xy~C~v1yC+x or xC+yvn^iy++x is
an (n l)cycle, so we may also assume that yv\,yvni ^ E(G). Since y can
have at most four nonadjacencies, yv2 must be an edge of G, and G contains the
(n l)cycle xC~yv2C+y~x. Thus, if x has exactly three nonadjacencies, G is
pancyclic. Having exhausted all cases, we may conclude that G is pancyclic.
To see that this result is sharp, consider the graph G* defined as follows:
Let V(G*) {to,. .. tni} and construct the hamiltonian cycle C =
v0vi... nn_iVq in G*. Selecting x v0 arid y = vn_ki for some k satisfying
4 < k < we let xvt be an edge for each i^0,2,n k 3,n k + l,n 2
and yvj be an edge for each jfy2,n k 3,n k 1, n h + l,n 2. Then
d(x) + d(y) 2n 10, but G* contains no (n l)cycle. See Figure 3.3.
3.2 Distancedependent Bounds
Theorems 3.4 and 3.5 provide sharp results, and are important for com
pleteness. The fact that the required degree sum is so large, while in some ways
surprising, also makes them somewhat unsatisfying. We return to the notion in
troduced in [13] and examine the cycle structure of G when x and y are allowed
34
to lie farther apart on a hamiltonian cycle. We begin by considering the case
where the distance between x and y is two.
Theorem 3.6 Let G be a graph of order n with hamiltonian cycle C. If there
exist x.y G V(G) such that distc{x,y) = 2 and d(x) + d(y) > n + 1, then G is
pancyclic.
Proof: Let C vqv^ . cn_ii'0. where .r = c0 and y = We separate
the proof into two cases based on whether xy is an edge of G.
Suppose that xy is an edge of G and consider the graph G' G un_i.
This graph contains a hamiltonian cycle C' x, ty,. .., tn3, y, x and dc{x) +
dGfy) > n 1. Consequently, by Theorem 2.14 G' is either pancyclic, bipartite,
or missing only an (n 2)cycle. If G' is pancyclic, then G is also pancyclic and
we are done.
Suppose then that G' is bipartite, and note that that x and y must lie in
opposite partite sets of G'. Since G' is hamiltonian. each partite set of G' must
have order Furthermore, if we let U' and W denote these partite sets and
assume, without loss of generality, that x G U and y G W then the fact that
da'{x) + dGfy) = n 1 implies that x is adjacent to each vertex in W and y is
adjacent to each vertex in U. Since x and y are consecutive on the hamiltonian
cycle C", we see that for each 2 < t < there is a cycle of length 2t in G'
(and hence G) that contains the edge xy. To obtain cycles of odd length in G
we simply replace xy with the path xvn^py to obtain a cycle of length 21 + 1 for
each t. These cycles, along with C and the triangle xvniyx, imply that G is
pancyclic.
35
Now suppose that both G' and G do not contain an (n 2)cvcle. We
then consider the following pairs of possible edges in G1: (vqV\ ^2^4);
(V0V2, vn2Vni) and {v0Vi,vn2Vi2), where 3 < i < n 3. For convenience,
we will refer to this collection of pairs as Aq. We claim that if both elements
of anv of the pairs in A0 are in E(G'), then G' would contain a cycle of length
n 2.
Indeed, were both elements of either (v0vi. vn_2vni) or {xQV2,vn2vnz)
edges in G', it is not difficult to see that G' must contain a cycle of length
n 2. If both elements of (vqvu un_2u,;_2), where 3 < i < n 3, were edges in
G, then VQViC+vn2Vi^2C~ v0 is an (n 2)cycle in G'.
Consequently at most one element of each pair in A0 is an edge of G', and
hence of G. Since there are n 3 pairs and u0un_2, u0u_i and un2Wi are all
edges of G, dc(x) + dG(y) < n 3 + 4 = n + 1. Therefore equality must hold
and exactly one element from each pair in Aq must be an edge of G.
Similarly, examine the pairs (wcTi, W2W5), W2^4), (^0^3, W2W3)
and (vqVi, vn2Vi2), where 4 < i < n 3. For convenience, we will refer to this
collection of pairs as Ay. As is the case with A0, at most one element from each
pair in Ax is an edge of G'. Using an argument similar to that given above, this
implies that exactly one element from each pair in Ax must be an edge of G.
By assumption, vn2vn3 is an edge of G and therefore, as (un_2un_3, v0v3)
is in Ax, VqVz cannot be an edge of G. As (v0v3, vn_2vx) is in Aq, vn_2vx must be
an edge of G. However, it then follows that vxv2 ... un_2rq is an (n 2)cycle in
G, contradicting our supposition. Thus if xy is an edge of G, G is pancyclic.
36
Suppose that xy is not an edge of G. Note first that since dG(x) + dG{y) >
n + 1, one of x or y must have degree at least Np arid hence must be adjacent
to two consecutive vertices on C. This implies that G contains a triangle.
Assume then that G does not contain a cycle of some fixed length l > 4.
Then at most, one element of each the pairs (lyv^ c_2'fg4+z), where 1 < i <
n I + 1, and each of the pairs vn2Vj). where 1 < j < f 3, is an
edge of G. Indeed, were it the case that for some i, both vqV( and vn_2Vi+ei
were edges in G, then VQVlC+vl+^4Vn^2C+Vo would be a cycle of length i in G.
We handle the situation where both and vn2Vj are edges in G in a
similar manner.
Since there are n 2 of these pairs and both v0vni and cn_2nni are edges
of G, d(x) + d(y) < n 2 + 2 = n, which contradicts the hypothesis that
d(x) + d(y) > n + 1. Hence, if xy is not an edge of G, G is pancyclic.
The following corollary is an immediate consequence of Theorem 2.15 and
Theorem 3.6, since the conditions imply that there must be two vertices of degree
sum at least n + 1 at distance one or two apart on a hamiltonian cycle of G.
Corollary 3.7 If G is hamiltonian with more than  vertices of degree at least
then G is pancyclic.
As the vertices x and y are moved farther apart on the hamiltonian cycle,
it becomes possible for cycle lengths to be missing from the graph. Those cycle
lengths that may be missing from G are determined both by the degree sum of
x and y along with the distance between x and y on the hamiltonian cycle.
Theorem 3.8 Let G be a graph of order n with hamiltonian cycle C and let
37
k be an integer satisfying 1 < k < . If there exist x,y 6 V(G) such that
distc(x, y) = k+l and d(x) + d(y) > n + k. then G contains cycles of all lengths
Â£, where 3 < Â£ < n k. This result is sharp.
Proof: Let C vqV\ . where x = u0 and y = unfci If there
is a vertex 2 in the path P = vn_kvnk+i vni that is adjacent to both x
and y, then the cycle C' = xC+yzx is a hamiltonian cycle of the graph G'
induced by V(G) V(P) + ,2, which has order n k + 1. In G\ distcfx, y) = 2
and dcfx) + defy) > n + k 2(k 1) = (n k + 1) + 1, so by Theorem
3.6 G' is pancyclic. Consequently, G contains cycles of all lengths Â£, where
3<Â£
Suppose that there is no vertex 2 e V(P) that is adjacent to both x and
y. Since d(x) + d(y) > n + k, x and y have at least k common neighbors, all
of which must be in V(G) {V(P),x,y}. We separate the proof into two cases
based on whether or not xy is an edge of G. For both cases we will consider the
graph G" induced by V(G) V(P).
Suppose that xy is an edge of G. The cycle C" xC+yx is a hamiltonian
cycle of G" with dc{x,y) 1 and defx) + dciy) > n + k k = n. Since
V{G")\ = n k and k > 1, G" is pancyclic by Theorem 2.15 and so G contains
cycles of all lengths l, where 3 < Â£ < n k.
Now suppose that xy is not an edge of G. An observation similar to that
made in the proof of Theorem 3.6 yields that G contains a cycle of length 3.
As such, we will suppose that G contains no cycle of length Â£, for some fixed Â£
between 4 and n k. Recall that x and y are nonadjacent, share no neighbors in
P and have a degree sum of at least n + k in G. As a result, these two vertices
38
have at least k + 2 common neighbors in G" and dG"{x) + dciy) > n.
We consider pairs of possible edges in G. as above. If 4 < L < k + 2, let A0
denote the collection of pairs (t'ocy. i'rivib+to). where l
and let denote the pairs (to^(n/t1)(Â£2)+Ja VnkiVi+j), where 1 < j < Â£ 4.
The reader should note that tnA'iG3 appears in pairs from both .4! and .42
while vn_k\V\ appears in neither. Additionally, it is useful to note that each
vQi\, for 2 < i < n k 2 appears exactly once in A0 U Ai as does each ye,,
save the ones already mentioned, for 2 < j < n k 2.
We claim that if more than one element from any of these pairs is an
edge in G, then G would contain a cycle of length Â£. Indeed, consider
{vaViiVnkiVi+ii) Â£ A0, where l
elements of this pair were edges in G. Note that since x and y have at least
k + 2 common neighbors, there must be at least one such common neighbor v'
that does not lie in the set {c,,.... 4}. Then v0v'vnkiVe+i4C~ViV0 is a
cycle of length Â£ in G.
Next, consider (v0v^ki)(e2)+j,VnkiVi+j), where 1 < j < Â£ 4, and
assume that both elements of this pair were edges in G. Then
v0C+vj+iXnkiC~V(n_k_i)_(e_2)+jVo is an Â£cycle in G.
Hence exactly one element from each of the n k 2 pairs in A0 U A\ can
be an edge of G. Taking into account that ViVnki may be an edge of G, and
recalling that either x or y, but not both, may be adjacent to each vertex in P,
we have that d(x) + d(y) < n k 2 + k+ l = n 1. This contradicts the
hypothesis that d{x) + d(y) > n + k.
39
Figure 3.4: d(x) + d(y) > n + k, but G has no cycle of length longer than
n k
nk n1
Figure 3.5: d(x) + d(y) = n + k 1, but G contains no cycle of length ^
Hk + 3<Â£
that for each of the pairs (v0vi:vn_ki vek+i3), where l
(vovne+ij, vnkiVk+2j), where n Â£ + 2 < j < n 2kl, at most one element
is an edge of G. There are n 2k 1 of these pairs and none of the 2k possible
edges VQVn_k~i and tVicTT where 1 < i < k, lie in any pair. This implies that
d(x) + d(y)
that d(x) + d(y) > n + k.
Therefore G contains cycles of all lengths Â£ ior 3 < Â£ < n k. This result is
sharp in the sense that, for 2 < k < the graph in Figure 3.4 (for readability
the its are suppressed in Figures 3.4 and 3.5) has two vertices x and y satisfying
d{x) + d{y) >n + k and dc(x,y) = k + 1, yet there are no cycles longer than
40
n k. We also note that if we lower the degree sum of x and y
some cycles of length i for 3 < C < n k. As an example see
which d(x) + d(y) = n + k 1, but there is no cycle of length 
that 2 < k <
. we may miss
Figure 3.5 in
provided
41
4. Cycles in Bipartite Hamiltonian Graphs
When studying hamiltonian graphs, and cycles in general in graphs, it is
quite common to look for bipartite variations of a given result. However, a
bipartite graph cannot be pancyclic, as it cannot contain cycles of odd lengths.
We consider a bipartite graph of order 2n to be bipancyclic if it contains cycles of
all even lengths from 4 to 2n. In this chapter we will prove results for bipartite
graphs that are analogous to those in the previous chapter. We begin by stating
the classic result of Moon and Moser [17] that gives the Ore type condition for
bipartite graphs.
Theorem 4.1 (Moon, Moser 1963) If G is a balanced bipartite graph of or
der 2n with parts X and Y in which d(x)+d(y) > n for every pair of nonadjacent
vertices x e X and y EY, then G is hamiltonian.
If we add the condition that G is hamiltonian in the assumptions, how much
can we relax the degree sum conditions in order to assure that G is bipancyclic?
Schmeichel and Mitchem showed that having two vertices of high degree sum
close together on a hamiltonian cycle of G suffices.
Theorem 4.2 (Schmeichel, Mitchem 1982) Let G be a bipartite graph con
taining hamiltonian cycle C = ViV2 .. .v2n. If d(vi) + d(v2n) > n + 1, G is
bipancyclic.
Theorem 4.3 (Schmeichel, Mitchem 1982) Let G be a bipartite graph con
taining hamiltonian cycle C = vpv2 .. .v2n. If d{y2) + d{v2n) > n + 2, G is
bipancyclic.
42
The above two theorems will be used to as a starting point in the sections
that follow.
4.1 Absolute Bounds for Bipartite Graphs
We begin this section by determining the degree sum of two vertices on
a hamiltonian cycle, regardless of their placement, required to assure that a
bipartite graph is bipancyclic, obtaining results analogous to those for graphs.
We start with the following two useful lemmas.
Lemma 4.4 Let G be a bipartite hamiltonian graph with parts X and Y such
that \X\ = \Y\ =n> 4 and let C be a hamiltonian cycle of G. If there exists a
vertex v G V(G) of degree n 1, then G is bipancyclic.
Proof: Let C = xay0x\yi... xi2/niA), where v = x0 and let Pi, 1 < i <
n 2, be the vertex nonadjacent to v. If vye is an edge of G, then the cycle
C' = vyiC~v is a cycle of length 2{I + 1) in G, so our assumption implies that G
contains cycles of all even lengths except possibly a cycle of length 2(z + 1). We
may assume without loss of generality that i 1, otherwise we would consider G
in the counterclockwise direction. Then vyiC+yi+lv, is a 2(i + l)cycle. Hence,
G is bipancyclic.
Lemma 4.5 Let G be a bipartite hamiltonian graph with parts X and Y such
that  A = Yj = n > 6 and let C be a hamiltonian cycle of G. If there exists
a vertex v G V{G) of degree n 2, then G is either bipancyclic or missing only
the 2(n 1 )cycle.
Proof: Let G = x0y0xiyi... xniyn_ix0, where v = xq and let yi,yv
l
43
G contains cycles of all even lengths except possibly 2(?' + 1) and 2(j + 1). If
i = 1 and j = n 2. then G may not contain a 2(r? l)cycle. For all other i,j
there are chords vyk. vye, vym and vyp, k < Â£ and rn < p. such that vykC+yev
is a 2(z + l)cycle and vymC+ypv is a 2(j + l)cyc,le. Hence G is bipancyclic or
missing only the 2(n l)cvcle.
Similar to the case for graphs, when considering a hamiitonian bipartite
graph with two vertices of high degree sum, placing no restrictions on their
proximity on a hamiitonian cycle, the sum that guarantees the graph is bipan
cyclic is close to the order of the graph. The results for bipartite graphs come
in pairs, as we must consider the case in which the vertices are in the same part
separately from the case in which they are in different parts.
Theorem 4.6 Let G be a bipartite hamiitonian graph with parts X and Y such
that X = y = n > 8 and let C be a hamiitonian cycle ofG. If there exist
u,v V(X) such that d{u) + d(v) > 2n 5, then G is bipancyclic. This result
is sharp.
Proof: Assume that G is not bipancyclic, and let C = x^y^xiyi... xniyn^iXo,
where v = Xq, be a hamiitonian cycle in G. Since d{u) + d(v) > 2n 5, we may
assume without loss of generality that d(v) is at least n 2. Lemmas 4.4 and
4.5 therefore imply that v has degree exactly n 2 and that G is missing only
the 2(n l)cycle. As such, we can see that and 2 must be the vertices
of G that are not adjacent to v. We now consider the vertex u V(X), which
has degree at least n 3.
44
It is useful to note that if u was either .ly or ;r_i, this would place u and
v distance exactly two apart on a hamiltonian cycle, implying that G would be
bipancyclic by Theorem 4.3. Thus we may assume u is neither xy nor xn\.
Since u has at most three nonadjacencies, and two of these must be u and
i/+++, at least one of uy2 and ayn~2 is an edge of G. We will assume without loss
of generality that uyn_2 is an edge. If u ^ x_2 then C = xqC+ uyn2C~u+z\)
is a hamiltonian cycle. If u = xn_2 then either uy0 or uy\ is an edge of G arid
G contains the 2 (n l)cycle
uyoC+u xqCu
or
uyiC+u~x0C~u.
Thus G is bipancyclic.
To see that this result is sharp, consider the graph G* defined as follows:
Let V(G*) = V{X) U V(Y), where V(X) = {x0, xu..., xn^} and V{Y) =
{yo, 2/1,, yn~i}, and construct the hamiltonian cycle C = x0y0xiyi... xn_xyn_ix0.
Choose v = xq and u xn^2 with vy%, uyj an edge for all i ^ l,n 4,n 2,
j 7^ l,n 4, n 1. Then d(u) + d(v) 2n 6, but G* does not contain a
2(n l)cycle. See Figure 4.1.
Theorem 4.7 Let G be a bipartite hamiltonian graph with parts X and Y such
that X = Yj = n > 8 and let C be a hamiltonian cycle of G. If there exists
v e V(X) and u V(Y) such that d(u) + d(v) >2n 4, then G is bipancyclic.
This result is sharp.
45
Figure 4.1: d(u) + d(v) = 2n 6, hut G* contains no cycle of length 2(r? 1)
Proof: Assume that G is not bipancyclic, and let C xQy0Xiyi... xn^iyn^ix0
where jj = lo, be a hamiltonian cycle in G. Since d(u) + d(v) > 2n 4, we may
assume without loss of generality that d(v) is at least n 2. Lemmas 4.4 and
4.5 therefore imply that v has degree exactly n 2 and that G is missing only
the 2(n l)cycle. As such, we can see that yi and yn_2 must be the vertices of
G that are not adjacent to v. We now consider the vertex u E V(Y), which has
degree at least n 2.
Note that if u was either y0 or yn_i, this would place x and y consecutive
on a hamiltonian cycle, implying that G would be bipancyclic by Theorem 4.2.
Thus we assume u is neither yQ nor yni Since G contains no 2(n l)cycle, the
nonadjacencies of u must be u and u+++. If it ^ yn~3 then G contains the
2(n l)cycle x0C+uxn_iC~u++x0. If u = yn3 then G contains the 2(n 1)
cycle uxiC+u xqC~u. Hence G is bipancyclic.
To see that this result is sharp, consider the graph G* defined as follows:
Let V(G*) = V(X) U V(Y), where V(X) = {xQ, xi:..., xni} and V(Y)
{y0, yi,, yn_ 1}, and construct the hamiltonian cycle C x0t/o^i?/i ^nWni^o
Choose v = x0 and u yn_3 with vyi,uxj an edge for all i 7^ l,n 2 and
46
j 7^ 1, n 4. /? 1. Then d(u) + d(v) = 2ri 5. but G* does not contain a
2 (n. l)cycle.
4.2 Distance Dependent Bounds for Bipartite Graphs
We consider the effects of moving the two vertices of large degree sum farther
apart on a hamiltonian cycle. We begin by considering the case that G has two
vertices of large degree sum a distance three apart on a hamiltonian cycle of G.
Lemma 4.8 Let G be a bipartite graph of order 2n with hamiltonian cycle C =
V\Vi V2n If d(vi) + d(v2n2) > n + 2, then G is bipancychc.
Proof: Let x = and y = v2n2 Suppose xy G (G). Define G' to be the
graph induced by V{G) U2niW2n Then G' contains the hamiltonian cycle
C' xC+yx. Since G' has order 2(n 1) and dG'{x) + dG'{y) >n = (n 1) +1,
G' is bipancyclic by Theorem 4.2. Hence G is bipancyclic.
Suppose xy $ E(G) and further suppose that G does not contain a cycle of
length 2Â£ for some Â£, 2 < Â£ < n 1. Then at most one of the elements of each
pair (xv2i, yv2e+2i5), where l
of some pair were edges of G, then xv2iC+V2e+2isyC+x would be a 2fcycle in
G. Similarly, at most one of the elements of each pair (xu2(nr+j) j Uv2j+i), where
1 < j < Â£ 2, is an edge of G. If both elements of some pair were edges of
G, then G would contain the 2fcycle xv2(ne+j)C+yv2j+iC~x. There are n 2
of these pairs. Together with the edges yv2n\ and xv2n all possible adjacencies
of x and y are accounted for. This implies that d(x) + d(y) < n 2 + 2 = n,
which contradicts the assumption that d(x) + d{y) > n + 2. Consequently, G is
bipancyclic.
47
As the vertices x and y are moved farther apart on the hamiltonian cycle,
it becomes possible for cycle lengths to be omitted from the graph. As with
graphs, those cycle lengths that may be missing from G are determined both
by the degree sum of x and y along with the distance between x and y on the
hamiltonian cycle.
Theorem 4.9 Let G be a bipartite graph of order 2n with hamiltonian cycle
C = vpV2 .. i2n and let k be an integer satisfying 2 < k < n 1. If d(vi) +
d(v2(nk+i)) > n + k, then G contains cycles of all lengths 21, for 2 < I < n k.
Proof: Let x = V\,y = v2(nk+i) and P = V2(nk)+sC+v2n. Observe that
x and y are in different parts and that there are 2k 2 vertices between x
and y on C. Suppose that xy G E(G). Define G' to be the graph induced by
V(G) V(P). Then G' contains the hamiltonian cycle C' = xC+yx. Since G'
has order 2n (2k 2) 2(n k + 1) and dc(x) + defy) > n + k (2k 2) =
(n k + 1) + 1, G' is bipancyclic by Theorem 4.2. Therefore G contains cycles
of all lengths 21, for 2 < I < n k.
So we may assume that xy f E(G). Suppose there exist u,v G V(P) such
that uv G E(C) and yu,xv G E(G). Define G' to be the graph induced by
V(G) V(P) + u,v. Then G' contains the hamiltonian cycle C' = xC+yuvx.
Since G' has order 2n (2k 2) + 2 = 2(n k + 2) and dofx) + defy) >
n + k (2k 2) + 2 = (n k + 2) + 2, G' is bipancyclic by Lemma 4.8. Thus
G contains cycles of all lengths 21 for 2 < l < n k.
We may now assume that x and y have no consecutive neighbours in V(P),
and so dp(x)+dp(y) < k 1. Suppose that G does not contain a cycle of length
48
2Â£ for some Â£. 2 < ( < n k. We will consider two cases.
Case 1: Let 2 < Â£ < k + 2. For each of the pairs (xv2(e+i~i),yv2i+i), where
1 < i < n k Â£+ 1. at most one element is an edge of G. If both elements were
edges of G, then G wrould contain the 2Ccycle xv2(i+ii)C+yv2i+iC~ x. The edges
xv2j for 1 < j < 1 and yv2m+\ for nk Cf 2 < m < n k are not included in
the pairs, and may therefore be edges of G. There are nkÂ£+ 1 possible edges
from the pairs and Â£ 1 + (n k (n k Â£ + 2) + 1 = 21 2 possible unpaired
edges in G P.x. y. Since xy is not an edge of G and dp{x) + dp(y) < k 1.
wre have
d(x) + d(y) < n k Â£ + 1 + 2Â£ 2 + k 1 = n + Â£ 2 < n + (k + 2) 2 = n + k.
This contradicts the assumption that d(x) + d(y) > n + k, so G must contain
cycles of all lengths 21, 2 < Â£ < n k.
Case 2: Let k + 3<Â£
edges: (xv2lJyt.2(e+ik)i) for 1 < i < n Â£ and (xv2(ne+j),yvx(j+k)3) for 1 <
j < Â£k. In each pairing, at most one element is an edge of G or G would contain
the 2Ccycle xv2lC+v2(e+ik)iyC+x or xvx{j+k'j_3C+yv2^n_e+j)C~x, respectively.
Since k + 3 < Â£ and 2 < k, 2{Â£ k) + 1 < 2Â£ 3. Hence the only possible edges
not considered in the pairings are the edges yv2i+\ for 1 < i < k 2. Recall
that xy is not an edge of G and that x and y have no common neighbours in P.
Therefore
d(x) + d(y) < (n k) + (A; 1) + (k 2) = n + k 3,
which contradicts the assumption that d(x) + d(y) > n + k. This contradiction
completes the proof.
49
Theorem 4.10 Let G be a bipartite graph of order 2n with hamiltonian cycle
C = viV2... t'2n and let k be an integer satisfying 3 < k < n 1. If d(vx) +
d{v2(nk)+3) > n + k, then G contains cycles of all lengths 21, for 2 < I < n k.
Proof: Let x = vu y = v2(nk)+3 and P v2(n_k+2)C+v2n Observe that x
and y are in the same part, and that there are 2k 3 vertices between x and y on
C. Suppose there is a vertex 2 G V(P) such that 2 is adjacent to both x and y.
Define G' to be the graph induced by V(G) V{P) + Then G' contains the
hamiltonian cycle C' = xC+yzx. Since G' has order 2n (2k 4) = 2(n k + 2)
and dc(x) + def y) > n + k (2k 4) = (n k + 2) + 2, G' is bipancyclic by
Theorem 4.3. Hence G contains cycles of all lengths 21, for 2 < Â£ < n k.
So we may assume that x and y have no common neighbours in V(P).
Suppose that G does not contain a cycle of length 21 for some i, 2 < I < n k.
At this time we note that x and y have at least k common neighbours. We will
consider two cases to complete the proof.
Case 1: If 2 < I < k 1, then x and y have a common neighbour not
in the path U2iC,+u2(r+i2), for 1 < i < n I + 1. Since G does not contain
a 2Â£cycle, at most one element of each pair (xv2i,yv2(i+i^2)), where 1 < i <
n k Â£ + 3, is an edge of G. If both elements of some pair were edges of
G, then for some common neighbour 2 not in the path v2iC+v2(e+i2), G would
contain the 2tcvcle xv2lC+v2(p+l2)yzx. Additionally, at most one element of
each pair (xv2(nkt+j+2),yv2j), where 1 < j < Â£ 1, is an edge of G. If both
elements of some pair were edges of G, then xv2(n_k~e.+j+2)C+yv2]C~x would
be a cycle of length 2Â£. There are n k + 2 of these pairs, which account for
all possible adjacencies of x and y in V(G) V(P) x,y. As x and y have no
50
common neighbours in V(P). this means that d(x)+d(y) < (n k + 2) + =
n + 1. However, d(x) + d(y) > n + k > n + 3. Therefore we may assume that
k < Â£ < n k.
Case 2: If k < l < n k, then at most one of each pair (xv2i,yv2(ek+i)),
where 1 < z < n Â£+ L is an edge of G. If both elements of some pair were edges
of G. then G would contain the 2Tcycle xv2iC+i'2(ek+i)yC+x. Additionally, at
most one element of each pair (xv2(nke+j+2)yv2j), where 1 < j < Â£ 1,
is an edge of G. If both elements of some pair were edges of G, then as in
case one xv2(nke+j+2)C+yv2jC~x would be a cycle of length 2Â£. There are
n 1 of these pairs, which account for all possible adjacencies of x and y in
V(G) V(P) x, y. Recall that x and y have no common neighbours in V(P).
So we have that d(x) + d(y) < (n 1) + \ n + k 2. This contradicts
the assumption that d(x) + d(y) > n + k, and so G must contain cycles of all
lengths 2Â£ for 2 < Â£ < n k.
51
5. Conclusion
We conclude with open problems and new directions. In Chapter 2 we
presented many results on Favoiding hamiltonian graphs. One of the directions
remaining to be explored in that area is the bipartite variations of the results
given. In our investigation of these questions we have encountered more open
problems, such as determing the classes of graphs that are the exceptions to
Moon and Moser's result Theorem 4.1.
In Chapter 4 we presented results for bipartite graphs that are analogous
to the results of Chapter 3. However, the general results were all shown to be
sharp, whereas the bipartite results were not. It is our belief that the results
presented are not best possible and can be improved upon.
In addition to answering these questions, we have begun to investigate prism
hamiltonian graphs. The cartesian product G = G1DG2 has V(G) = V(G 1) x
V(G2), and two vertices (ui,u2) and (vi,v2) of G are adjacent if and only if
either
1. U\ = V\ and u2v2 Â£ E{G2) or
2. u2 = v2 and U\Vi Â£ (Gh).
The prism of a graph G is the graph GOK2. We say that a graph G is prism
hamiltonian if GHK2 is hamiltonian.
A completely different direction that we have taken is the study of graph
saturation. Let F = {Hi,... ,Ht} be a family of graphs. A graph G is F
saturated if G does not contain any member of F, but for any pair of nonadjacent
52
vertices x and y in F(G). G + xy contains some member of F. We consider graph
saturation from the perspective' of games on graphs. We introduce the game of
Fsaturator, in which two players begin with the vertices of a graph G and none
of its edges. The players alternately add edges of G in such a way as not to
create any graph in F. For some specific families F and graphs G we have been
able to determine when there is a winning strategy for one of the players.
53
REFERENCES
[1] A. Ainouche, N. Christofides, Conditions for the existence of Hamil
tonian circuits in graphs based on vertex degrees, J. London Math. Soc. (2).
32, 1985, no. 3, pp. 385391.
[2] R.E.L. Aldred, D.A. Holton, M.I. Porteous, M.D. Plummer,
Two results on matching extensions with prescribed and proscribed edge
sets, Discrete Math, 206, 1999, pp. 3543.
[3] R.E.L. Aldred, D.A. Holton, Z.K. Min. A degree characterization of
pancyclicity. Discrete Math, 127, 1994, pp. 2329.
[4] D. Amar, E. Flandrin, I. Fournier, A. Germa, Hamiltonian pan
cyclic graphs, Discrete Math, 46, 1983, p. 327.
[5] B. Bollobas, G. Brightwell, Cycles through specified vertices, Com
binatorica, 13, 1993, pp. 147155.
[6] J. A. Bondy, Pancyclic Graphs, Journal of Combinatorial Theory, Series
B, 11, 1997, pp. 8084.
[71 J. A. Bondy, V. Chvatal, A method in qraph theory, Discrete Math.,
15, 1976, pp. 111136.
[8] Gary Chartrand, L. Lesniak, Graphs and Diagraphs, Chapman &
Hall/CRC Press, Boca Raton, Florida, 2005.
[9] G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc.,
2, 1952, pp. 6981.
[10] Y. Egawa,Edgedisjoint Hamiltonian cycles in graphs of Ore type, SUT J.
Math, 29, 1993, no. 1, pp. 1550.
[11] R. Faudree, C. Rousseau and R. Schelp, EdgeDisjoint Hamiltoni
ain Cycles, Graph Theory with Applications to Algorithms and Computer
Science, 1984, pp. 231249.
[12] M. Ferrara, R. Gould, G. Tansey, T. Whalen, Disjoint Hamilto
nian Cycles in Bipartite Graphs, submitted.
54
[13] S. L. Hakimi. E. F. SCHMEICHEL, A Cycle Structure Theorem for Hamil
tonian Graphs. Journal of Combinatorial Theory, Series B. 45, 1988. pp.
99107.
[14] D. Hayes. E. Schmeichel, Some extensions of Ore's theorem, Graph
theory with applications to algorithms and computer science, Kalamazoo,
Mich., 1984. pp. 687695. WileyIntersci. Publ., Wiley. New York.
[15] H. KRONE, A generalization of a theorem of Posa, Proc. Amer. Math. Soc..
21, 1969. pp. 7778.
[16] J. Mitchem. E. Schmeichel, Bipartite graphs with cycles of all even
lengths, J. Graph Theory, 6, 1982, pp. 429439.
[17] J. Moon, L. Moser, On hamiltonian bipartite graphs. Israel J. of Math.,
1, 1963, pp. 163165.
[18] C. Nara, On sufficient conditions for a graph to be Hamiltonian, Natur.
Sci. Rep. Ochanomizu Univ., 31, 1980, no. 2, pp. 7580.
[19] L. Ng, M. Schultz, kOrdered hamiltonian graphs, J. Graph Theory, 1,
1997, pp. 4557.
[20] O. Ore, A Note on Hamilton Circuits, Amer. Math. Monthly, 67, 1960, p.
55.
[211 L. POSA, On circuits of finite qraphs, Magyar Tud. Akad. Mat. Kutato Int.
Kozl., 8, 1963, pp. 355361.
[22] R. J. Gould, Advances on the hamiltonian problema survey, Graphs
and Combinatorics, 19, 2003, no. 1, pp. 752.
[23] R.J. Gould, A Look at Cycles Containing Specified Elements of a Graph,
to appear in Discrete Math.
[24] R. Shi, 2Neighborhoods and Hamiltonian conditions, J. Graph Theory, 16,
1992, pp. 267271.
[25] A.G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs,
Ann. Discrete Math, 3, 1978, pp. 259268.
[26] C. Thomassen, Independent dominating sets and a second hamiltonian
cycle in regular graphs, Journal of Combinatorial Theory, Series B, 72,
1998, pp. 104109.
55
[27] C. THOMASSEN, On the number of hamiltonian cycles in bipartite graphs,
Comb. Prob. Comput.. 5. 1996, pp. 437442.
[28] W.T. Tutte. On hamiltonian circuits. J. London Math. Society, 21, 1946,
pp. 98101.
[29] Douglas B. West, Intorduction to Graph Theory, 2nd Edition. Prentice
Hall, Saddle River, NJ, 2001.
56
