A SURVEY ON THE GRACEFUL LABELING OF
GRAPHS
by
R. Lynn Watson
B.S., Roanoke College, 1972
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
2000
This thesis for the Master of Science
degree by
R. Lynn Watson
has been approved
by
Richard Lundgren
Sylvia Lu
Date____L
Watson, R. Lynn (M.S., Applied Mathematics)
A Survey on the Graceful Labeling of Graphs
Thesis directed by Professor Richard Lundgren
ABSTRACT
A graph G is said to be graceful if the numbers used to label its vertices are dis-
tinct values of the set {0,1,.... m}, and the edge labels are the set {1, 2,m},
where the edge labels are the absolute value of the difference of the vertex
values. Graceful labeling grew from Ringels Conjecture, which states that
for a given tree T with n vertices and n 1 edges, the edges of the complete
graph K2V.-1 can be partitioned into 2n 1 trees isomorphic to T. Ringels
Conjecture is one of the major unsolved problems of graph theory. The ex-
istence of a graceful labeling for a graph implies Ringels Conjecture is true
for that graph. It is this relationship between graceful labeling and Ringels
Conjecture that has created the interest and research in graceful labeling. This
is a survey paper exploring the history of the prolonged and prolific interest in
the graceful labeling of graphs, as well as the algorithms for gracefully labeling
a variety of graphs, including paths, caterpillars, lobsters, k-ary trees, planar
grids, cylindrical grids, and balanced trees.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed
Richard Lundgren
l)]
DEDICATION
To my sons Brian Collison, Greg Collison, and Luke Egbert for their unending
patience and support.
ACKNOWLEDGEMENTS
I would like to thank Rich Lundgren for his guidance and patience.
I would also like to thank Stephen Billups and Sylvia Lu for their time and
support in serving on my thesis committee.
CONTENTS
Figures ..................
Chapter
1. Introduction...........
2. Paths..................
3. Caterpillars...........
4. Grids..................
4.1 Planar Grids ........
4.2 Prisms...............
5. Coronas................
5.1 Wheels...............
5.2 Crowns ..............
6. Cycles with a Chord .
7. Trees .................
7.1 Balanced Trees . .
7.2 K-ary Trees..........
7.3 Trees of Diameter four
7.4 Lobsters.............
8. Conclusion.............
References................
vii
1
n
l
10
13
14
18
22
22
25
30
34
35
38
41
51
55
57
FIGURES
Figure
1.1 A complete graph on 7 vertices partitioned into 7 trees with 3 edges 2
1.2 Gracefully labeled graph............................................... 3
1.3 A gracefully labeled tree and K?n-i................................... 4
1.4 A gracefully labeled path............................................. 5
1.5 A caterpillar......................................................... 5
2.1 A path............................................................... 7
2.2 A gracefully labeled path Pn where n is even......................... 8
2.3 A gracefully labeled path Pn where n is odd.......................... 8
2.4 An a-gracefully labeled path........................................... 9
3.1 A star.............................................................. 10
3.2 A gracefully labeled caterpillar .................................... 11
3.3 A caterpillar which is gracefully labeled............................ 11
4.1 A grid on a plane.................................................... 13
4.2 C3OP2 The Cartesian product of a 3-cycle and a path with two
vertices ............................................................. 14
4.3 Graceful labeling J of Pm ............................................ 14
4.4 Labeling R(x) obtained from J...................................... 15
4.5 Graceful labeling I\ of Pm............................................ 15
4.6 Labeling S(x) obtained from K....................................... 16
Vll
4.7 Graceful labeling J of P5.......................................... 16
4.8 Labeling R(x) obtained from J...................................... 17
4.9 Graceful labeling K of P5 ......................................... 17
4.10 Labeling obtain from K......................................... 18
5.1 Corona C5 0 P2................................................. 22
5.2 Initial labeling of vertices in Ah 0 C&............................ 23
5.3 Graceful labeling of K4 Cs....................................... 24
5.4 Gracefully labeled graph I\\ C9................................. 25
5.5 The crown C5 O Ah................................................ 26
5.6 Graceful labeling of Gs O AT....................................... 27
5.7 Graceful labeling of Ce AT....................................... 27
5.8 Graceful labeling of Ce O AT....................................... 28
5.9 Graceful labeling of C7 AT....................................... 29
6.1 Gracefully labeled C4 with chord.................................. 31
6.2 Gracefully labeled Ce with chord skipping one vertex.............. 31
6.3 Gracefully labeled Ce with a chord skipping two vertices.......... 31
6.4 Gracefully labeled C14 with a chord skipping one vertex........... 31
6.5 Gracefully labeled C14 with a chord skipping two vertices......... 32
6.6 Gracefully labeled C14 with a chord skipping three vertices .... 32
6.7 Gracefully labeled C\4 with a chord skipping four vertices........ 32
6.8 Gracefully labeled C\4 with a chord skipping five vertices........ 33
6.9 Gracefully labeled C44 with a chord skipping six vertices......... 33
7.1 Attempting to gracefully label a graph after adding a pendant vertex 34
7.2 Construction of a balanced tree.................................... 35
7.3 Gracefully labeled graphs S and T................................... 36
7.4 Eight copies of T which have been relabeled......................... 37
7.5 Graceful labeling of graph U........................................ 38
7.6 Binary trees S and T................................................ 39
7.7 Relabeling copies of T.............................................. 39
7.8 Gracefully labeled graph U.......................................... 40
7.9 Relabeling the gracefully labeled third generation binary tree ... 40
7.10 Gracefully labeled binary tree of four generations................. 41
7.11 Gracefully labeled quaternary trees S and T........................ 41
7.12 Graceful labeling of the third generation quaternary graph U . . 42
7.13 Gracefully labeled graphs 7\ and T2................................ 43
7.14 Gracefully labeled F, the uv-join of fi and /2..................... 43
7.15 A tree T of diameter 4......................................... 44
7.16 Gracefully labeled tree with n odd and S{ even..................... 49
7.17 Gracefully labeled tree of diameter 4.............................. 53
7.18 Gracefully labeled lobster L of diameter 6......................... 54
IX
1. Introduction
This is a survey paper of graceful labeling, which has been an area
of interest in graph theory for almost forty years. The interest in graceful
labeling grew from the discussion of the decomposition of a graph G or a
partitioning of the edges E(G) into pairwise edge-disjoint subgraphs. A graph
G with n vertices and m edges consists of a vertex set V{G) = {i>i,...,un}
and an edge set E{G) = {ei,...,em}, where each edge consists of two vertices
called its endpoints. Further a tree is a connected graph with no cycles and
Kn is a complete graph of n vertices such that each of the vertices has an edge
connecting it to every other vertex. In the decomposition of a graph the easiest
case is to decompose the graph G into single edges. Soon more questions were
asked. Can a graph G be decomposed into subgraphs isomorphic to a tree T
of more than a single edge? If | E(G) | is a multiple of | E(T) |, can G be
decomposed into isomorphic copies of T? Are there some types of graphs which
can be decomposed easier than others? Can we decompose regular graphs,
complete graphs, trees or cycles? Are there any patterns?
In 1963, Ringel [1] conjectured the following:
Conjecture 1 Let T be a given tree with n vertices and n 1 edges; then the
edges of I\2n_i can be partitioned into 2n 1 trees isomorphic to T.
Figure 1.1 shows the conjecture for T, a tree of 3 edges, and K7. Tree T has 4
vertices or n = 4. Per Conjecture 1 there are 7 distinct copies of T in K7. It
1
T
K2n-1
Figure 1.1. A complete graph on 7 vertices partitioned into 7
trees with 3 edges
is interesting to consider the number of edges in A^n-i relative to the number
of edges in T. The number of edges in K2n-i is equivalent to the number of
ways one can choose 2 from the group 2n 1 or
(2n 1)(2n 2)
2n1
2
= (2n l)(n 1).
Therefore, the number of distinct edges in K2n-i is always (2n 1) times
| E(T) |. It remains to be proven that the partitioning results in trees
isomorphic to T, but we know there exist the correct number of edges.
In 1966 Rosa [11], reports Kotzigs stronger conjecture as stated here:
Conjecture 2 Let T be a given tree with n vertices and n 1 edges, then the
complete graph I\2n-\ can be cyclically partitioned into 2n 1 trees isomorphic
to T.
This cyclic partitioning is accomplished for an arbitrary T by identifying a
suitable set of edges in K2n-i and rotating each node and edge from its orig-
inal position 2n 1 times. Conjecture 2 is referred to as the Ringel-Kotzig
conjecture. The difference between Conjecture 2 and Conjecture 1 is the idea
that the partitioning can be done cyclically, which is a stronger requirement.
2
Certainly, if Conjecture 2 is true, then Conjecture 1 is also true.
A graph G with m edges and n vertices can be labeled in such a way
that the vertices are numbered and each edge is assigned a label equal to the
absolute value of the difference of its vertex labels. A graph G is said to be
graceful if the numbers used to label its vertices are distinct values of the set
{0,1,..., m}, and the edge labels are the set {1,2,..., m}, where the edge labels
are the absolute value of the difference of the vertex values. The function
assigning values to each vertex v of G is denoted by f(v). An example of a
graceful labeling is in figure 1.2. It should be noted that these labelings are
not usually unique. It should also be noted that the vertex labels are distinct
values of the set {0,1,2,..., m}, not the complete set. It is possible to label the
vertices in such a way as to produce two edges with the same label, which does
not produce a graceful labeling.
Figure 1.2. Gracefully labeled graph
Alexander Rosa introduced the idea of graceful labeling in 1967 [11].
Rosa [11] then proved the following theorem.
Theorem 1 If a tree T with n vertices and n 1 edges has a graceful labeling,
then there exists a cyclic partitioning of the complete graph K^n-i into 2n 1
subgraphs isomorphic to T.
3
0
Figure 1.3. A gracefully labeled tree and K2n-i
Proof. View the vertices of I\2n-i as the congruence classes mod
2n 1. The displacement between two congruence classes is the number of
unit moves needed to get from one to the other. The maximum displacement
between two congruence classes mod 2n 1 is n 1. The edges of /<2n-i
consist n 1 displacement classes, each of size 2n 1. In other words one
displacement class is all edges whose vertices are 1 unit apart and another
displacement class is all edges whose vertices are 2 units apart so there are 4
displacement classes in the example (figure 1.3).
From a graceful labeling of T, we define copies of T in A^n-i fr
0 < k < (2n 1) 1. In the kth copy, the vertices are k,..., k + (n 1)
mod 2n 1, with k + i adjacent to k + j if and only if i is adjacent to j in the
graceful labeling. The 0th copy of T looks just like the graceful labeling and has
one edge with each displacement. If there is an edge from each displacement,
there is an edge of each length and the graceful labeling has been maintained.
Moving to the next copy shifts each edge to the next edge in its displacement
class. Hence the 2n 1 copies of T cycle through the 2n 1 edges from each
displacement class, without repetitions, and these 2n 1 copies of T decompose
I<2n-
Rosas work and, in particular, this theorem launched the field of
4
graceful labeling. Then Rosa made the following conjecture.
Conjecture 3 All trees are graceful [10].
Ringels Conjecture is one of the major unsolved problems of graph theory. The
existence of a graceful labeling for a graph implies Ringels Conjecture is true
for that graph. It is this relationship between graceful labeling and Ringels
Conjecture that has created the interest and research in graceful labeling. Con-
jectures 1 and 2 remain two of the major unsolved problems in graph theory,
which is the reason the topic of graceful labeling has such activity.
A path is defined as a graph such that every vertex has degree at most
2 and exactly two vertices have degree 1. Rosa [11] proved that the simplest
tree, a path, is graceful. Figure 1.4 shows an example of a gracefully labeled
path.
---------> m--------------
0 6 15 2 4 3
Figure 1.4. A gracefully labeled path
A caterpillar (see figure 1.5) is defined as a graph such that deletion
of every vertex of degree one results in a path.
Rosa [11] proved all caterpillars are graceful. Zhao [15] proved all
trees of diameter four are graceful. An underlying idea in the graceful labeling
of larger graphs is that of joining two or more gracefully labeled graphs and
5
being able to gracefully label the resulting graph. This idea is explored in
several chapters of this paper. In this survey paper we will explore algorithms
for graphs that have been proven to be graceful and apply these algorithms to
examples. The primary area of interest is trees, although we will also look at
the graceful labeling of grids, crowns, coronas and cycles with a chord. The
interest in graceful labeling of graphs other than trees is tangential to the
graceful labeling of trees and the search for patterns leading to the graceful
labeling of all trees. We must define a few more terms and the scope of this
study before proceeding. A loop is an edge whose endpoints are equal. Parallel
edges or multiple edges are edges whose endpoints are the same. A simple
graph is a graph with no loops or parallel edges. A connected graph is a graph
such that there exists an edge between any two subsets of the graph. In this
paper only connected simple graphs are considered. Some related topics not
discussed in this thesis are sequential labeling, harmonious labeling, Skolem
graceful, edge graceful, and rotatable graceful.
Graceful labeling grew from Ringels and Kotzigs discussion of graph
decomposition. Rosa proved iiGn-i has a decomposition into 2n 1 copies T
if T is a tree with n edges and can be gracefully labeled. This thesis explores
the history of graceful labeling and discusses the results of graceful labeling
different types of graphs. The algorithms for gracefully labeling a variety of
graphs are presented for the general cases and demonstrated for specific cases.
6
2. Paths
A graph is called a path (see figure 2.1) if the degree d(v) of every
vertex, v, is < 2 and there are no more than 2 endvertices [14]. An endvertex
or leaf is a vertex of degree 1.
-----------------------------------
Figure 2.1. A path
Theorem 2 Every path is graceful [11].
Proof. We demonstrate an algorithm to gracefully label any path Pn
with n vertices. In a path the number of edges is one less that the number
of vertices or m n 1. Labeling can begin at either end without loss
of generality. The first vertex at one end is labeled 0, the adjacent vertex
is labeled n 1, the next adjacent, non-labeled vertex is labeled 1, and we
continue in this manner. Alternate vertices are incremently increasing by 1
while the remaining vertices are incremently decreasing by 1. Consider two
cases where n = 0(mod 2) and n = l(mod 2) shown in figures 2.2 and 2.3
respectively. In both cases k = [|J.
For the even case the edge labels beginning with the leftmost edge in
figure 2.2 are | (n 1) 0 |, | (n 1) 1 |, | (n 2) 1 |,..., [ (n k) (k 1) |=
n l,n 2,n 3,..., 1. In determining the last edge value recall k [|J. For
cases where n is even, k = |_f J = f and (n k) (k 1) = n k /c + l = l. It
is easy to see this is a graceful labeling since all numbers between 1 and n 1
7
or m are used in the edge labels.
Similarly, when n is odd the edge values beginning on the left are
n l,n 2, n 3,1. In evaluating the right most edge value, recall k
Lf J = when n is odd. Then n k k = n !k=A- = 1. Again every
value from 1 to n 1 or m is used.D
--------------------------------------------------------------------------............-------------
n-1 1 n-2 2 n-3 3 k-1 n-k
Figure 2.2. A gracefully labeled path Pn where n is even
-------------------------------------------------------------.............------------
n n-1 1 n-2 2 n-3 n-k k
Figure 2.3. A gracefully labeled path Pn where n is odd
Rosa [13] also introduced a-graceful labeling, which is a stronger stan-
dard, and therefore fewer graphs are a-graceful. Graphs that are a-graceful
are also graceful. A graceful graph G is said to be a-graceful if there exists
a critical value a such that for every edge (u,v), either f(u) < a < f{y) or
f{y) < a < /(it). In each a-graceful graph, a is a positive integer and the
vertices are said to have an a-valuation. These a-graceful graphs must be bi-
partite, which implies that no a-graceful graphs can have an odd cycle [3]. An
example of a-graceful labeling is shown in figure 2.4, where a = 3. Examine
the vertex labels in the path shown in figure 2.4. Beginning at the left end of
the path the first vertex is labeled 0 and alternate vertices to the right increase
by 1. Call these vertex labels {0,1,2,3} set A. While the left most vertex
adjacent to vertex 0 is n 1 and each alternate vertex to the right decreases
by 1. Call these vertex labels {6,5,4} set B. Sets A and B appear to converge
8
---------- -----
0 6 1 5 2 4 3
Figure 2.4. An a-gracefully labeled path
to a value from the lower and upper sides respectively. In other words the
values belonging to set A are less than or equal to some value and the values
belonging
a-graceful
to set B are greater that the same value. This is what is meant by
labeling, where a is this value to which is set A and B converge.
9
3. Caterpillars
Deleting every endvertex of a caterpillar results in a path. This path
is called the spine of the caterpillar. What if the resulting path is one vertex
or a point? Then the graph prior to deletion of end vertices is called a star as
shown in figure 3.1. A star is a special case of caterpillar.
Figure 3.2 shows the gracefully labeled caterpillar from figure 1.5.
The first vertex on the spine is labeled 0 and the adjacent vertices are labeled
{24,23,22,21,20} using the higher values on the leaf neighbors, so that 20
is the label for the next vertex on the spine and there are 4 leaf neighbors of
vertex 0. Now the remaining non-labeled neighbors of 20 are labeled {1,2,3,4}
with the lower values on the leaf neighbors and the value 4 on the next vertex
on the spine. Continuing in this manner the caterpillar of 25 vertices is labeled.
The edge values are {1,2,3,..., 24} and m = 24, while the vertex values are
from the set {0,1,2, ...24}. Therefore this labeling is a-graceful.
Theorem 3 All caterpillars are a-graceful [11].
10
Figure 3.2. A gracefully labeled caterpillar
Proof. We demonstrate an algorithm to a-gracefully label any cater-
pillar. Let Vi represent the vertices on the spine of the caterpillar and N(v{) the
neighborhood of V{, that is, the set of all vertices adjacent to u,-, while |Af(uj)|
is the number of vertices which are adjacent to V{.
k{ = <
I N(v,) | -1,
I N(v,) | -2,
if i is the first or the last vertex of the spine
otherwise
Figure 3.3. A caterpillar which is gracefully labeled.
(1) Begin by labeling the first vertex on the spine 0 (figure 3.3). Alternate
vertices of this spine beginning with the first vertex are called odd. All
other vertices on the spine are called even.
(2) Leaf neighbors of 0 are labeled beginning with n 1 and going in
descending order ending with n ki where ky = N(v0) 1.
(3) The next vertex on the spine, a neighbor of 0, is labeled n (ky +1).
11
(4) Leaf neighbors of this vertex n (ki -f 1) are labeled 1 through k2.
(5) Continue in this manner. The odd vertices on the spine and the leaf
neighbors of the even vertices on the spine are labeled in increasing
order, while the leaf neighbors of the the odd vertices on the spine and
the even vertices on the spine are labeled in decreasing order. The last
vertex on the spine is labeled n (kx + k3 + + &i;_i + ]) if it is even.
It is k2 + k4 + + ki-1 + ^ if odd. The last neighbor of this vertex is
labeled k2 + k4 + ki-2 + k{ + or n (fci + k$ + + k{-2 + k{ + [|J)
respectively.
(6) a = min {x,y} where x = the label of last vertex on the spine and,
{min{ labels of leaf neighbors }, if x < labels of leaf neighbors
max{ labels of leaf neighbors }, if x > labels of leaf neighbors
In the example in figure 3.2 a = min{9,10,11,12,13,14,15,16} = 9.D
12
4. Grids
A grid is a graph defined as the Cartesian product of two graphs.
Grids are not trees and not directly related to the proof of Ringels conjec-
ture (Conjecture 1). However, interesting work has been done in the area of
gracefully labeling grids, as we show in this chapter. The Cartesian product
GOH of graphs G and H whose vertex set is V(G) x V(H) can be defined as
follows. Let u be a vertex in V(G) and v be a vertex in V(H). Then (u,v) is
an element of GOH and (u,v) is adjacent to (u', v1) if and only if
(1) u = u1 and edge vv' belongs to E(H) or
(2) v = v' and edge uu' belongs to E(G) [14] (see figure 4.1). The grid
shown is a planar grid P3DP5, where Pm is a path with m vertices.
a3 b3 c3 d3 e3
b2 c2 d2
al bl cl dl el
Figure 4.1. A grid on a plane
Another type of grid is a cylindrical grid CmOPn as shown in figure
4.2, where Cm is a cycle of length m. Imagine a cylindrical grid as the grid
from figure 4.1 on the curved surface of a cylinder. The last type of grid,
CmOCn, is on a torus. Following are algorithms for gracefully labeling planar
13
G n H GDH
Figure 4.2. C3OP2 The Cartesian product of a 3-cycle and a
path with two vertices
and cylindrical grids respectively.
4.1 Planar Grids
Theorem 4 The graph PmUPn has an a-valuation or a-graceful labeling [9].
Jungreis and Reid [9] developed the following algorithm. Note: This
algorithm assumes m < n. If m > n, find a graceful labeling for PnOPm and
use the transpose of the resulting labeling as if it were a matrix.
(1) Let J represent the graceful labeling of Pm (figure 4.3).
------------------------------------------------------............-------------
0 n>-l 1 m-2 2 k-1 m-k
Figure 4.3. Graceful labeling J of Pm
(2) Let x = k(2m 1) and R(x) be the labeling that results from adding
(2mn 2m n + 1) x to the higher values in the J labeling and
adding x to the lower values (figure 4.4), where i 0,1,2,...,
(3) Let K = (m 1) J represent another graceful labeling of Pm (figure
4.5). This alternate labeling is also called the complement with respect
to m 1.
14
--------------------------------------------*..........------------
x 2mn-m-n-x x+1 2mn-m-n-l-x x+2 x+k-1 2mn-in-n-k+l-x
Figure 4.4. Labeling R(x) obtained from J
(4) Let x = k(2m 1) + (1 m) and S(x) be the labeling obtained by
adding (2ran 2m n + 2) x to the higher values in the I\ labeling
and adding x to the lower values (figure 4.6), where k = 1,2,..., The
definition of x is different for the functions R and S.
R(x) and S(x) are the foundation for the graceful labeling of the grid PmUPn.
Each column of the grid is a copy of Pm and there are n columns. The first
column is the {2k + 1)5< copy where k 0. The labeling in that column and
all odd numbered columns will be determined by the function R{k{2m 1)),
where k = 0,1, ,The labeling in even numbered columns or 2kth copies
will be determined by S{k(2m 1) + (1 m)), where k = 1,2, , |.(Note:
The raised quantities st and th in the previous expressions are not exponents,
but suffixes as in ls< or 5th.)
This algorithm produces an a-graceful labeling [9]. Examine the table
of values below to see that the odd columns of the grid are labeled according to
the function R(x) while the even columns are labeled using the function S(x).
The odd rows of the R(x) function begin with 0 and incremently increase. The
even rows begin with the highest value in the grid and incremently decrease.
For the S(x) function the odd rows begin with a higher value and decrease,
-------------------------------------------..........-----------
m-l 0 m-2 1 m-3 m-k k-1
Figure 4.5. Graceful labeling K of Pm
15
----------------------------------........--------
2mn-m-n+I-x x 2mn-m-n-x x+1 2mn-m-n-l-x 2mn-m-n-k+2-x x+k-1
Figure 4.6. Labeling 5'(s) obtained from K
while the even rows start with smaller values and increase. This means adjacent
vertices are approaching a middle value from below and above. This middle
value is a.
0 2 mn 2m n + 1 2 m 1 2mn n + k 2 km
2 mn m n m 2 mn 3m n + 1 2 km k m + 1
1 2 mn 2m n 2m 2 mn n + k 2 km 1
2 mn m n 1 m + 1 2mn 3m n 2km k m + 2
2 2mn 2m n 1 2m + 1 2 mn n + k 2 km 2
V -1 2 mn 2m n p + 2 2m + p 2 2 mn n + k 2km p + 1
2 mn m- n- p+ l m + p 1 2 mn 3m n p + 2 2km k m + p 1
The following example illustrates the process for P5DP6. In P5DP6, m = 5
and n = 6. First, gracefully label P5 as shown in figure 4.7.
------------------------
0 4 13 2
Figure 4.7. Graceful labeling J of P5
Next calculate 2mn 2m n + 1x and add the result to the higher
labels of J and add x to the lower labels of J to obtain labeling R(x) (figure
4.8).
2 mn 2m n + 1 x 2(5) (6) 2(5) (6) + 1 x = 45 x
Develop an alternate graceful labeling I\ of P5 using K = (m 1) J,
which is the complement with respect to m 1 (figure 4.9).
16
--------------------------------------
x 49-x x+1 48-x x+2
Figure 4.8. Labeling R(x) obtained from J
Now add 2mn 2m n + 2 x to all higher values of labeling K and
add x to all lower values of K to obtain labeling S(x) (figure 4.10).
2 mn 2m n + 2 x = 2(5) (6) 2(5) (6) + (2) x 46 x
If k = 0, (2k + 1) = 1, use R(k(2m 1)) = #(0(2(5) 1)) = R(0).
R( 0) = 0,49,1,48,2
If k = 1, (2k) = 2, use S(k(2m 1) + (1 m)) = 5(1(2(5) 1) + (1 5)) = 5(5).
5(5) = 45,5,44,6,43
If k = 1, (2k + 1) = 3, use R(k(2m 1)) = #(1(9)) = #(9)
#(9) = 9,40,10,39,11
If k = 2, (2k) 4 use S(k(2m 1) + (1 m)) = 5(2(9) 4)) 5(14)
5(14) = 36,14,35,15,34
If k = 2, (2k + 1) = 5 use R(k(2m 1)) #(18)
#(18) = 18,31,19,30,20
If k = 3, (2k) 6 use S(k(2m 1) + (1 m)) 5(3(9) 4)) = 5(23)
5(23) = 27,23,26,24,25
The labels form the matrix shown below. Each value represents a
vertex in the grid. Examination shows this is a gracefully labeled grid and
---------------------------------------
4 0 3 1 2
Figure 4.9. Graceful labeling I\ of #5
17
X
49-x
x+1
48-x
50-x
Figure 4.10. Labeling S(x) obtain from K
closer examination reveals that it is a-graceful where a = 24.
0 45 9 36 18 27
49 5 40 14 31 23
1 44 10 35 19 26
48 6 39 15 30 24
2 43 11 34 20 25
4.2 Prisms
The prism (also called cylindrical grids) is defined as the Carte-
sian product CmOPn where n > 2 [7].
Jungreis and Reid [9] developed algorithms for the cases m = 0(mod
4) for any n and m = 2(mod 4), n = 0(mod 2). They have not developed an
algorithm for m = 2(mod 4) and n = l(mod 2) or for m = l(mod 2). Building
on this work, Huang and Skiena [7] developed algorithms for all cases where
m = 0(mod 2). When m = l(mod 2) and 3 < n < 12 they use these same
algorithms for the first m 3 columns and use computers to produce tables for
the values in the last two columns.
Frucht stated [3] that all prisms were graceful and he would so show
in a later article, but so far, he has not shown this result. Frucht [4] proved
that all prisms with n = 2 are graceful. Thus far, it has not been proven that
all prisms with odd cycles are graceful.
18
Theorem 5 All prisms are graceful if they have no odd cycles [3].
The following examples use the algorithm given by Huang and Skiena. Graceful
labeling of prisms with even cycles falls into two primary cases depending upon
whether m is divisible by 4.
CASE 1) When m = 0(mod 4) or C4p[I].Pn, use the following labeling.
= {in L|J + liJ )6(i + j + !) +
((2n ~ 1 )m in + - LfJ ~ 4|j) <*(*' + j)
where ie{0,1, 2,m 1} labels the column, je{0,1,2,n 1} labels the row,
5(x) = 2(mod 2), and each row in the matrix of values represents one copy of
C*4p.
When the parity i + j is odd, 8{i + j) = 1 and 5{i +J + 1) = 0, so that
the first term in the labeling function f(i,j) = 0 and the value at this vertex
is determined by the second term of the labeling function. When the parity of
i + j is even, the opposite happens and the first term of f(i,j) determines the
value. The table below shows the values for the prism C^mPs, where p = 1
and n = 5.
0 1 2 3
0 0 32 9 18
1 36 5 22 14
2 1 31 10 17
3 35 6 21 15
4 2 30 11 16
19
CASE 2) When m = 2(mod 4), there are again two cases, depending on the
parity of n. Part A will address the case where n = 0(mod 2) and Part B will
deal with the case for n = l(mod 2).
Part A) For m = 2(mod 4), m > 6, n > 4, and n = 0(mod 2) or C4P+2OP2q
where p>l,q>2 Huang and Skiena use a different presentation of Jungreis
and Reids algorithm which is shown here.
f{i,j) = {in LfJ + [i\)8{i + j + 1) +
((2n 1 )m-in+ [fj n[%j) 6{i + j)
The example shown in the table below is for the prism where p = 1
and q = 2 or m = 6 and n = 4.
0 1 2 3 4 5
0 0 39 7 28 14 20
1 42 4 35 11 24 17
2 1 38 8 27 15 19
3 41 5 34 12 23 18
Part B) Form = 2(mod4) and n = l(mod 2) or C4P+2OP2q+1 where p > l,q > 1
the labeling is defined as
f{i,j) = {in L|J + LiJ +nL|J)^ + i +!) +
((2n l)m -in+ Li J) + !)
for i < m 3. This labels the vertices in all of the columns except the last
two. The labels for the vertices in the next to the last column are given by the
following labeling:
20
f(m 2,0) = H n + 2,
f(m 2,1) = H -f 2n, where // = {2n-\)m ^ ancj
/(m 2,j) = (H + 2n- l^j) S(j) + (H + in + [i 2j) i(; + 1),
for j > 2.
The labels for the vertices in the last column are defined as
f(m 1, 0) = if n + 1,
f(m l,n 1) = H + 3(n~1); and
f(m 1 ,j) = (H+ [itij) i(j) + (if + n Lj + lj) S(j + 1),
for 1 < j < n 2.
Using the prism C^D-Ps (p '= 1 and g = 2) as an example, the resulting
vertex labels are shown in the table below.
0 1 2 3 4 5
0 0 50 9 41 24 23
1 54 5 45 19 37 27
2 1 49 10 40 46 30
3 53 6 44 20 35 28
4 2 48 11 39 47 33
21
5. Coronas
Coronas are a class of graphs created by joining two or more graphs.
The corona G\ OG2 of two graphs G\ and G2 is the result when the two graphs
are joined in the following way. Assuming G1 has p\ points, one copy of G\ is
used and p\ copies of G2 are used. The ith point of G\ is joined to every vertex
in the ith copy of G2 [3] (figure 5.1).
5.1 Wheels
The wheel is the corona Ii\ Cn where I*
Wheels can also be described as the result of adding a center to an n-gon where*
n > 3 and making this center adjacent to every vertex in the n-gon by adding
the appropriate edges [3] (see figure 5.2).
Theorem 6 Wheels are graceful graphs [3].
In order to gracefully label wheels consider two cases n = 0(mod 2)
or n = l(mod 2).
22
CASE 1) n = O(mod 2) First number the vertices of the wheel so
that the center of the wheel is vq and the remaining vertices are given values
Vi, u2,vn sequentially. Now use the following algorithm to relabel the vertices
and obtain a graceful labeling.
2n i 1
if i=2,4,6,...,n-2
/(*>)
2
<
i
if i = n 1
if i = 0,1,3,5,..., n 3
2n if i = n
For n S use the following example. First label the vertices uo,ui,i>2, ...v$ as
shown in figure 5.2.
Figure 5.2. Initial labeling of vertices in K\ C&
Per the algorithm uo, Ui, U3, and v5 are relabeled 0, 1, 3, and 5
respectively. The vertex vs is labeled 2n or 16 and v-j is labeled 2. Now
the remaining even-numbered vertices i>2, ^4, and V6 are relabeled with the
complement with 2n 1 i resulting in 13, 11, and 9 respectively (see figure
5.3).
23
16
13
3
5
Figure 5.3. Graceful labeling of Ki 0 Cs
CASE 2) Consider n l(mod 2) or odd. Begin by labeling the
vertices as in Case 1 with vq,vi,v2, ...vn. The algorithm for relabeling each
vertex is only slightly different from Case 1.
f(vi)
2i if i = 0,1, or n
* n + i if i = 2,4,6..., n 1
n + 1 i if i = 3,5, 7,..., n 2
For n 9 examine the following example as shown in figure 5.4. First label
the vertices uo, ui, V2,...vg as shown.
For v0, Vi, and u9 relabel each vertex with 2i or 0, 2, and 18 respec-
tively. For all even vertices add n or 9 to the index to get the value of the
label. For all remaining odd vertices use n + 1 i, resulting in 7, 5, and 3
respectively.
24
2
1"
13
15
Figure 5.4. Gracefully labeled graph K\ Cg
5.2 Crowns
A crown (figure 5.5) is a cycle Cn plus edges pendant at each vertex
[1]. The notation for a crown is Cn Ki, which is the reverse order of a wheel.
Frucht showed that all crowns are graceful [3] by using four cases
depending upon the parity of n (mod 4).
CASE 1) If n = 0(mod 4) a graceful labeling for CnQK\ is obtained by
using the following algorithm. First label the vertices of the cycle Vi,V2, ...,un
in order and label the vertex pendant to V{ by u* for i = 1, 2,..., n.
where n is the number of vertices in the cycle. Thus the edges of the cycle are
f(vi) = i,
2n + 1 i, if i = 2,4, 6,..., n
and
25
(i>i, u2), (v2, u3),(un_i, vn), (vn, ui) and the edges joining Cn to the pendant
points m are An example for n 8 is shown in figure 5.6.
CASE 2) If n l(mod 4), values for the vertices are given by
f(vi)
t-1, for odd i ^ ^
n 3, if=
2n + 1 i, if* = 2,4,6,..,2=i
2 n i, j n+3 n+7 n+ll 11 1 2 5 2 5 2 5 ' .., n 1
and
/
2 n-f{Vi), if* = 1,2,3,...,^
2n + 1 f(Vi), if i =
/() =
2n 2 if i
n+1
2
2n 1 /M. =
n.
An example using this algorithm where n 5 is shown in figure 5.7.
CASE 3) When n = 2(mod 4), there exists a graceful labeling given
by
26
1
Figure 5.6. Graceful labeling of C8 0 K\
Figure 5.7. Graceful labeling of C5 K\
27
and
'
i 1, for odd i ^ |
f-2, if = f
2n + 1 i, if i = 2,4, 6,| 1
2n-l, if i | + 1, ~ + 3, ...,n
2n f{vi),
if i = 1,2, 3,.
n
? 2
2
2n + 1 f{vi), if i = | 1
2n 2 /(ui), if i = f
2n-l-/(u,-), if i = f + 1, f + 2,
An example of using this algorithm to gracefully label a crown where n = 6 is
shown in figure 5.8.
12
Figure 5.8. Graceful labeling of Cq K\
CASE 4) When n = 3(mod 4), a graceful labeling is determined by
28
and
i 1,
/() = <
if* = 1,3,5,..., V-
n+3 n+7 7i+l 1
Xi = s?>
2 2
, ..., n
2n + 1 *, if i = 2,4,6, ...n 1
/() =
2n /(,-),
if* = 1,2,3, ...,=i
n+3 n+5
2 i
2n + 1 f(vi), if ^2 ,
An example of gracefully labeling a crown where n = 7
figure 5.9.
Figure 5.9. Graceful labeling of CV 0 Ki
is pictured in
29
6. Cycles with a Chord
A cycle with a chord is a cycle Ck with any two non-adjacent vertices
joined. It has been conjectured that these graphs can be gracefully labeled [3],
although it has not been proven. These graphs are another example of a class
of graphs formed by joining two or more gracefully labeled graphs, where the
first graph is a cycle and the second graph is a path of length one. I gracefully
labeled graphs of this nature for 4 < k < 14 as shown below. There are always
k + 1 edges and in labeling the vertices there are two numbers between 0 and
k T 1 that are not used. A pattern for assigning values to the vertices was not
found.
In drawing these graphs the chord can be drawn from any vertex with-
out affecting the labeling. Without loss of generality one vertex is selected as
the beginning of the chord, then chords will be drawn to each of the remaining
vertices. Due to symmetry it will be necessary to label only some of these
graphs to find graceful labelings of all Ck with a chord. In the graph C4, we
only need to consider one chord shown in figure 6.1. In the graph C&, there
are only two configurations we need to consider as shown in figure 6.2 and 6.3.
For C14, there are eleven possible chords and with symmetry it is sufficient to
examine and label only six of them (see figures 6.4-6.9).
30
0
Figure 6.1. Gracefully labeled C4 with chord
Figure 6.2. Gracefully labeled C6 with chord skipping one vertex.
Figure 6.3. Gracefully labeled Cq with a chord skipping two vertices
Figure 6.4. Gracefully labeled C14 with a chord skipping one vertex
31
Figure 6.5. Gracefully labeled Ci4 with a chord skipping two vertices
Figure 6.6. Gracefully labeled C\\ with a chord skipping three vertices
Figure 6.7. Gracefully labeled Ci4 with a chord skipping four vertices
32
Figure 6.8. Gracefully labeled Ci4 with a chord skipping five vertices
Figure 6.9. Gracefully labeled C14 with a chord skipping six vertices
33
7. Trees
A tree is defined as a connected graph with no cycles [14]. While
several classes of trees have been shown to be graceful, Ringels Conjecture
remains open. There are several problems in proving that all trees are graceful.
First, there needs to be an approach encompassing all trees instead of proving
a specific type of trees is graceful. Second, induction, which works well to prove
many characteristics of trees, hasnt worked to prove gracefulness. Induction
has traditionally been used on trees in the following manner. Given that a
tree of n vertices has characteristic b, delete a pendant vertex and assume
the remaining tree has characteristic b. For induction to work we must be
able to re-insert the pendant vertex anywhere and prove characteristic b exists
in the resulting tree. In ^-graceful labeling, and graceful labeling in general,
the placement of the vertex is critical to maintaining the graphs gracefulness.
Induction does not allow any assumptions about placement of the pendant
vertex and therefore, this type of induction cannot be used to prove gracefulness
of trees.
50423 60524 60524
S S' S
Figure 7.1. Attempting to gracefully label a graph after adding
a pendant vertex
34
In the following example shown in figure 7.1 graph S is o-gracefully
labeled. Graph S' and S" show how a pendant vertex can be added in two
different ways. S' is still a-gracefully labeled, while S" cannot be a-gracefully
labeled [2]. Possibly another approach using induction would work. In the
following sections we discuss balanced trees, k-ary trees, trees of diameter four,
and lobsters.
7.1 Balanced Trees
A balanced tree is defined in either of two ways. In both cases begin
with two trees S and T. To create the balanced tree attach a copy of T to
every vertex in S [12]. Another way to create a balanced tree is to attach a
copy of T to every vertex in S except one [12]. The second type of balanced
tree includes a special type of binary, ternary, and all k-ary trees. Figure 7.2
shows trees S and T with the resulting balanced tree JJ of the first type.
yu. y
S T
Figure 7.2. Construction of a balanced tree
If trees S and T are gracefully labeled, then U can be gracefully
labeled [12]. First, a fixed vertex in T is selected. This is the vertex that
35
will attach to vertices in S and is circled in figure 7.3. Assume | V(5') |= k
and vertices of S are labeled 0,1,...k 1. Make k copies of T labeled T,-,
i = 0,1,..., k 1. The fixed vertex in Tj will be labeled zn + 1 where | V(T) |= n.
S T
Figure 7.3. Gracefully labeled graphs S and T
| V{U) |= nk = 24 so that V(U) will be labeled 1 to nk. The
remaining vertices of T will be labeled in the following manner. The highest
remaining values will be adjacent to the fixed vertex with lowest value, so that
the fixed vertex To will be 1 and the remaining vertices in To will be labeled 24
and 23. The fixed vertex in Tl is labeled 4 while the remaining vertices in T\
will be labeled 21 and 20 since 21 and 20 are the highest remaining available
values. Continuing this way vertices adjacent to T7 are labeled 2 and 3. See
the values on the 8 copies of T in figure 7.4.
Proceed in the following manner [12]. First attach vertex 1 of To at the
end of graph S and call this uj as shown in figure 7.5. Next attach to neighbors
of Uj the remaining Tj with maximum value on the fixed vertex and call this
u22- Adjacent to u22, the remaining Tj with the minimum value on the fixed
vertex and call this u4. Continue in this manner alternating the maximum and
minimum values until all copies of T are attached to a vertex in S. Notice that
36
23 V 21 20 v 18 i2 v 15 i4 v
V i 4 V 7 10
12 J1 \/ V v \J
13 16 19 V 22
Figure 7.4. Eight copies of T which have been relabeled
37
the vertices in this balanced tree are labeled 1 to n instead of 0 to n 1. This
is caused by the notation used in Stantons and Zarnkes algorithm and could
be modified to be consistent with other authors. To achieve this modification,
label the fixed vertices in instead of in + 1 and let the labels of V{U) go from
0 to | V{U) | -1.
Figure 7.5. Graceful labeling of graph U
7.2 K-ary Trees
In the previous section the algorithm produces a gracefully labeled
tree by joining the gracefully labeled graphs S and T. The algorithm gives no
instruction for gracefully labeling the graphs S and T. In the case of balanced
k-ary trees the algorithm both labels and constructs the tree. A k-ary tree is
a rooted plane tree in which each vertex has no more than k children or edges.
In a balanced k-ary tree each non-leaf has exactly k children and every child of
the same generation has the same number of descendants. The binary tree and
all fc-ary trees are special cases of the balanced tree. In building a binary tree
38
so that it falls within the definition of a balanced tree, notice that the fixed
vertex is always the root of the initial tree.
1
1
2 3
s
2 3
T
Figure 7.6. Binary trees S and T
The algorithm [12] for the k-ary cases is different from the algorithm
used for other balanced trees. We will illustrate the algorithm first with an
example involving binary trees. Start with the binary trees S and T which are
a-gracefully labeled as shown in 7.6. Vertex 1 in T is the fixed vertex that
attaches to the vertices in S while vertex 1 in 5 is the designated vertex that
will not have a copy of T attached. Let | V(T) |= n. Relabel two copies of T
using (n + 1) u shown in figure 7.7, where u is the vertex label.
, 3 7 4
T,
Figure 7.7. Relabeling copies of T
Next add n -f 1 to the values in the odd rows and add 1 to the values
in the even rows of one copy of T. In the other copy add n + 1 to the even
rows and 1 to the odd rows (figure 7.7). Now the fixed vertices in the copies
39
of T are attached to the end vertices of S resulting in the new graph U (figure
7.8). The remaining vertex of S is labeled 1.
T,
2
2 6
Figure 7.8. Gracefully labeled graph U
To continue the process for a fourth generation, the new graph U is
relabeled using n T 1 u, where n =| V(U) | or 7. Add n + 1 or 8 to odd rows
and add 1 to even rows in one copy of U, while in the other copy add 8 to the
Figure 7.9. Relabeling the gracefully labeled third generation binary tree
The fixed vertex in U is the root and is attached to the end vertices
in S resulting in a binary tree of four generations as in figure 7.10.
Gracefully labeling a 4-ary or quaternary tree is the next example.
As in the binary case, S and T are initially identical and labeled as shown in
figure 7.11. Using n + 1 u or 6 to relabel T gives T' as shown in the same
figure. Use the idea from labeling balanced graphs in general to determine the
value to add to the odd and even rows in the four copies T;. Calculate in + 1,
values in the even row and add 1 to the values in the odd rows (figure 7.9).
40
15
8
13 14 10 11
Figure 7.10. Gracefully labeled binary tree of four generations
where i = 0,1,..., n 1 to get {1, 6, 11, 16}.
3 2
T
Figure 7.11. Gracefully labeled quaternary trees S and T
Add 1, 6, 11, 16 from this last calculation to the odd rows of T}, T2, T3, and T4
respectively. In the even rows add to Ti,T2,T3 and T4 respectively 16, 11, 6,
and 1. The result is shown in figure 7.12.
This pattern works for k-ary trees where k is even. When k is odd,
the middle copy has the same value added to even and odd rows.
7.3 Trees of Diameter four
It has been proven that all trees of diameter four are graceful [15].
Diameter is defined as the maximum distance between any two points in the
graph. We start with a discussion of certain graceful trees, which will lead to an
interesting result regarding lobsters. A lobster is a tree such that if all pendant
vertices were deleted, the remaining tree would be a caterpillar, which we show
in figure 1.5. Huang, Kotzig, and Rosa [6] proved the following Lemma, which
41
I
Figure 7.12. Graceful labeling of the third generation quaternary graph U
allows us to prove trees of diameter four are graceful. The un-join of Tj and
T2, denoted T Uv T2 is formed by joining the graphs at u and u (vertex u is
placed on vertex u) where ueV(Ti) and veV(T2) and the new graph has one
less vertex than | V(Ti + T2) |. Lemma 1 states that there exists a graceful
labeling for the un-join of Ij and T2, if either T\ or T2 is a-graceful and the
remaining tree is graceful.
Lemma 1 Let /j be an a-labeling of a tree Tj with /i(u) = 0 (where ueV(Ti)),
and let /2 be a graceful labeling of a tree T2 with /2(n) = 0 (where ueV(T2)).
Then there exists a graceful labeling of the tree T = T U" T2.
[Note: If T2 is a-graceful, then the resulting graph T is a-graceful as well.]
Define a labeling g of T by
/r(*)>
fr(z) + m,
fi(z) + a,
\
ifzehTOUu},
if zeViT^Mu],
if zeV(T2)\{n),
if z = u
/i() < oc,
fi(u) > a,
42
where a is the critical value in the a-graceful labeling of T\, f*(v) =| atfi(v) |,
= n fiiv), m is the number of vertices in T2, and n is the number
of vertices in T\. Wang, Ju, Lu, and Zhang refer to f*(v) and as the
inverse labelings of while others use the term complement with respect
to a or n respectively.
m = 20
Figure 7.13. Gracefully labeled graphs T\ and T2
Examine the gracefully labeled graphs T\ and T2 in figure 7.13. Fol-
lowing the algorithm, each vertex in the component from T2 will have its value
increased by 1, which is the value of a from /1. In the component from T\
the vertices whose value is less than or equal to a will be relabeled with
| a fi(u) \ {0,1, ...a}. Those vertices whose value is greater than a will be
relabeled with n fi(u) + m {1 + m, 2 + m,..., n (a + 1) + m}. These
values are shown in the uu-join of T\ and T2 in figure 7.14.
Figure 7.14. Gracefully labeled F, the uv-join of fi and f2
43
Shi-Lin Zhao [15] showed that all trees of diameter four are graceful
by developing an algorithm to gracefully label them. Trees of diameter four are
a class of lobsters and an example T is shown in figure 7.15. The approach Zhao
uses is also used by Huang [6] in gracefully labeling certain trees of diameter
four. The group of Wang, Ju, Lu, and Zhang uses a similar approach as a
premise for the graceful labeling of a special class of lobsters. Wang also used
this approach with Jin [8] to prove that all trees of diameter four are graceful.
This topic has created a lot of interest and many articles.
Figure 7.15. A tree T of diameter 4
Theorem 7 All trees of diameter 4 are graceful. [15]
In figure 7.15 call u,- and its neighbors component i. Every tree of diameter 4
must be similar to the one in figure 7.15. That is, there will exist some vertex x
that is adjacent to pendant vertices and to other vertices that are not pendant
vertices. These vertices can be categorized into three sets.
A = {u : d(x,u) 1, where u is a pendant vertex of T]
44
B = {v : d(x,v) = 1, where v is not a pendant vertex of T]
C = {v : d(x,v) = 2, where v is a pendant vertex of T}, where d(u,v) is the
distance from u to v.
We now describe to to label the vertices in these sets to produce a graceful
labeling of T.
Part 1) If n is odd and A = 0, let
n
s = where s; =| N(vi) | 1,
2 = 1
Si, if s, is odd
Si 1, if Si is even
D^) = \((s'r-1) + Us- 1)),
Z \r=i+1 r=l /
and D2{i) = ^ ( J2 (4 1) + - 1)
yr=n+l i r=l
Let k = and define the graceful labeling of T as follows:
f{x) = s + 2k + 2 (7.1)
f(vi) = s + 2k + 2 i, i = 1,2,...,k (7-2)
f(vk+j) = k + 2-j,j = 1,2, ...,k + 1. (7.3)
45
Equation 7.1 labels the center vertex x and equation 7.2 labels the vertices
in set B for i = 1,2while equation 7.3 labels the vertices in set B for
i k + 1, k + 2, ...k + j-
Before exploring the labeling of the leaf vertices, we need to examine
the notation used for a leaf vertex. The notation vl- designates the jth leaf
neighbor of u,- in set B. To label the leaf neighbors of set f?, that is set C, we
consider four cases:
(1) the leaf neighbor for j = 1,2,..., |(s'- 1),
(2) the leaf neighbor for j = 1) + 1, ^(s- 1) + 2,..., s'- 1,
(3) the leaf neighbor for j = st- 1, and
(4) the leaf neighbor for j = s;.
Case 1) For j = 1,2,..., |(s'- 1) and i 1,2,..., n,
/(})
s i D2{i) + k + 2 j,
s T i Di(i) k j,
if i < k
if i > k.
(7.4)
Case 2) For j (i)(;-l)+l,(l)(sl)+2,...,sj-l and i = 1,2
and also for j = s,- 1 when st- is odd,
D2(i) + 2 + & + 1+J 1), if i < k
Di(i) i + 3k + 2 + j 2(^4' 1)> if i k.
(7.5)
46
Case 3) For j = S{ 1 and s, is even,
/K') =
i + Difo) + k + 1,
i D\(i) k + s,
if f < k
if i > k,
(7-6)
Case 4) The labeling for the last vertex in each u,- is defined by f{v\.)
in each of the four sub-cases listed below.
Sub-case 1: If each s,- is odd for i 1,2, ...,n, then
/) =
i + D-2.(i) + k + 1, if i < k
i Di(i) k + s, if i > k.
Sub-case 2: If each s,- is even for i = 1,2, ...,n then
(7.7)
(i)s + i + k + 1, if i < k
fK)= . (7-8)
I (|)s -f- i k, if i > k.
Sub-case 3: If s is even, but some Sj in the set {si,52, ...,sn} are even and the
others are odd, then if s; is odd order the Vi such that i = 1,2, ...,a,n a +
l,n a + 2,...,n and if s, is even order the u,- such that i = a +1, a + 2,..., n a.
This ordering of n, puts the even Vi in the middle of the sequence and the odd
V{ at the beginning or the end so that a is the value of the subscript for the
odd S{ preceding the first even 5,-, while n a + 1 is the value of the subscript
for the first odd s,- following the last even s,-. Define f(vls.) for odd s, where
i = 1,2, ...a, n a + 1, n a + 2,..., n as in Case 1 and define f{vls.) for even S{
where i = a + l,a + 2,...,n a as follows.
47
<
(7.9)
/(<)
(|)s + i + k a + 1, li i < k
(|)s + i k + a, if i > k.
where i = a + 1, a + 2,n a.
Sub-case 4: If s is odd, but some 5,- in the set {si, S2,sn} are even and the
others are odd, then if s,- is odd order the V{ such that i = 1,2, ...a,n a,n a +
1,..., n and if s,- is even order the u,- such that i = a + 1, a + 2,..., n a 1. This
ordering of V{ puts the even w; in the middle of the sequence and the odd ut- at
the beginning or the end, while a is defined as in Sub-case 3. Define /(u*.) for
odd Si where i = 1,2, ...a, n a, n a + 1,..., n as in Case 1 and define /(v* )
for even s, where i = a + l,a + 2, a 1 as shown below.
(i)(s + 1) + i + k a, if i < k
/) = t7-10)
^ (^)(^ T 1) + % k + a, if > fc.
where i = a + l,a + 2,...,n a 1.
To apply these algorithms compare the value of j to 3,-. If j = s,-, use
the appropriate formula from equations 7.7-7.10. If j = s,- 1, use equations 7.6
for even s,- and equations 7.5 for odd Sj. If |(s(- 1) < j < s,- 1, use equations
7.5 and if j < |(s'- 1), use equations 7.4. The proof that this algorithm does
indeed produce a gracefully labeled graph is one of examining the edge values
of T. The algorithm only provides a graceful labeling for graphs of diameter
four where n is odd and A = 0. If n is odd and A ^ 0, then the component T'
of T that includes vertex x and A is cc-graceful since it is a caterpillar. T T'
is graceful from Part 1 and T must be graceful by Lemma 1.
Part 2) If n is even, let T' be A and let T" be one component incident to x
48
that does not include vertices of A, then T' U T" is a caterpillar and has an
a-graceful labeling. T T' T" is graceful by results in Part 1 and tree T is
graceful by Lemma 1.
We now demonstrate the algorithm by gracefully labeling the example
in figure 7.17. There are 5 vertices in set B and each st- is even.
Figure 7.16. Gracefully labeled tree with n odd and s; even
Begin by calculating the graceful values for vertex x and set B.
/(x) = s + 2& + 2 = 14 + 2(2) + 2 = 20
f(v{) s + 2k + 2 i = 14 + 2(2) + 2 i results in 19 and 18 respectively,
f(vk+j) = k + 2 j = 2 + 2 j which results in 3, 2, and 1 respectively.
In order to gracefully label the vertices in set C we need to calculate Di(i) and
Di{i). Since D\(i) is used only where i > k, find Di(3), Di(4) and -Di(5) and
similarly only find ^2(1) and Ã‚Â£^(2). To calculate D\(i) and /^(O we need the
values of s,- and s[ which are
5X = 2, s2 = 4, s3 = 4, s4 = 2, and s5 = 2
while Sj = 1, S2 = 3, S3 = 3, S4 = 1, and s'5 1
based on the previously shown definitions.
Di(3) = KM 1) + (4 1) + W-1) + -!)) = 5( + 0 + 0+1) = !
49
A(4) = |((4 -!) + - 1)) = 1(0 + 0) = 0
flip) = lebu -1)) = o
L r=6
ft(l) = 5((4-l) + 0) = |( + 0)=0
c2(2) = i((o) + (s;-i)) = i(o + o) = o
To assign values to Vj the next step is comparing the value of j to s?; and
determining which of the equations to use. Begin with the next to last vertex
in each s,- and work to the first vertex. The last vertex in each will be labeled
using one of the 4 sub-cases.
Since = s'A s'5 = 1 while s'2 s'3 = 3,
for v\ j = 1 and si 1 = 1 so that we use f{vls,) (equation 7.6) for assigning
values to the first vertex in Si,S4 and S5 and for assigning values to the third
vertex in S2 and s3.
f(v\) = 1 + 0 + 2+1 = 4,/K) = 4-0-2 + 14 = 16, f(v?) = 5-0-2 + 14 = 17
and f(v%) = 2 + 0 + 2 + l = 5 and /(v3) = 3 1 2 + 14 = 14.
The second vertex of s2 and s3 will be labeled by the second set of equations
(equation 7.5) because |(s(- 1) < j < Si 1.
f(v22) = 0 + 2 + 2 + 2 = 6 and /(u|) = 1 3 + 3(2) + 3 = 7.
Since j < |(s( 1) the value for the first vertex in s2 and s3 must be assigned
using the first set of equations (equation 7.4) so that
f{vl) = 14 2 0 + 2 + 1 = 15 and f{v\) = 14 + 3 12 1 = 13.
This leaves the last vertex of each s; to label, which will be done from equations
in Sub-case 2 since the sum of s; is even and each s,- is even.
f{v\) = 7 + l+2+l = 11, f{v\) = 7 + 2 + 2 + 1 = 12, /(u43) = 7 + 3 2 = 8,
50
/(u|) = 74-4 2 = 9, f(v52) = 7 + 5- 2 = 10
7.4 Lobsters
Lobsters are defined as trees that result in caterpillars when all pen-
dant vertices are deleted. It has been conjectured that all lobsters are graceful.
Wang, working with Jin, Lu, and Zhang, [8] showed gracefulness of a class of
lobsters. We examine the results of this study and show an example. To do
this Wang, Ju, Lu, and Zhang introduced definitions and lemmas regarding
moving components of a graph.
Definition Let u and v be two adjacent vertices of the tree T. By
deleting edge uv of T, T turns into two smaller trees u(T) and v(T). These
smaller trees are said to be components of T, and v(T) is called a component
incident to u.
Lemma 2 Let T be a graceful tree, / its graceful value function, u and v two
vertices of T, and u\ and u2 two pendant vertices adjacent to u. If
f{u i) + f{u2) = /() + f(v),
or
then the trees
and
2/(mi) = /O) + f{v),
T' = T uui uu2 + vui + vu2,
T" = T uui + vu i
are graceful trees with graceful value function/.
T' and T" are called components-moving trees of T.
51
Lemma 3 Let / be a graceful labeling of T(V\ E), p =| V |; then
(1) For any uvcE, we have
l{uv) =| }{u) f(v) | = | ~ Mf(v)) I
where l(vu) is the edge label of T;
(2) For every ueV(T), if
fM +f(u2) = f{u) +f(v),
or
2/(i) = f(u)+f{v),
then
Mf(u 0) + Mf(u 2)) = Mf(u)) + Mf(v))>
or
2<^p(/(i)) = Mf(u)) + <Ã‚Â£p(/(u))>
where <^p(/) = p /(u), veV(T) and /(u) is the graceful label of graph T1.
The authors refer to as an inverse transformation. It is the
same function used by Stanton and Zarnke and is called the complement with
respect to p. Lemma 2 states that the components-moving transformation
maintains the gracefulness of the graph. Lemma 3 proves that the graph will
still be graceful after applying the function 4>v. Using these lemmas, a new
class of lobsters with diameter greater than four can be gracefully labeled.
Begin with a graph T that is a collection of star trees whose center
vertices are all positive evens or positive odds. A star tree is made of a center
vertex connected to every other vertex. The star trees are joined by selecting
a pendant vertex from each and sticking them together. Label the vertices by
the algorithm described for caterpillars in section 3. Use the gracefully labeled
52
graph T from the earlier example in figure 7.17.
Figure 7.17. Gracefully labeled tree of diameter 4
First apply the function 4>p, which will change the label at vertex x
from 20 to 0. The label of 0 here is a requirement of Lemma 1. Now a path
of length 1 can be joined to graph T at the newly labeled vertex 0 and the
second vertex on the path will be labeled-according to the algorithm given with
Lemma 1 which is 20. Based on Lemma 2, components incident to 0 can be
moved. Specifically, the components containing tq and v5 can be moved to the
new vertex labeled 20 since iq and iq are labeled 1 and 19 respectively and add
to 20. This process will be repeated. First apply the function p, then add
a path of length one and finally move the components incident to vertex 20,
containing tq8 and v2 to vertex 0. Then the two components incident to vertex
0, containing vx and v4 can be moved to vertex 21. The resulting gracefully
labeled lobster shown in figure 7.18 has diameter six.
53
Figure 7.18. Gracefully labeled lobster L of diameter 6
54
8. Conclusion
The search for gracefully labeled graphs began in an effort to prove
Ringles Conjecture or Conjecture 1 (cf. [1], 1963). Just three years later Kotzig
developed the Ringel-Kotzig Conjecture (cf. [11], 1966). Rosa ([11], 1967)
introduced the idea of labeling vertices of the graph as a way of approaching
the proof of Ringles conjecture. Graceful labeling and a-graceful labeling
came from this study. Kotzig ([10], 1973) then conjectured that all trees are
graceful and Rosa (cf. [10], 1973) proved that Kotzigs Conjecture (Conjecture
3) implies Ringles Conjecture. In an effort to prove trees graceful Rosa proved
paths ([11], 1963) and caterpillars ([11], 1963) are graceful. Stanton and Zernke
([12], 1973) proved balanced trees formed from two graceful trees are graceful.
K-ary trees are a class of balanced trees proved graceful by Stanton and Zernke
([12], 1973). Lobsters are conjectured to be graceful ([6], 1982). Huang, Kotzig,
and Rosa ([6], 1982) proved that a gracefully labeled graph can be joined in
a certain way to an a-gracefully labeled graph to produce a gracefully labeled
graph. Zhao ([15], 1989)proved all trees of diameter four are graceful. Wang,
Ju, Lu, Zhang ([13], 1994) proved lobsters that begin as diameter four and are
changed by the components moving tree are graceful.
In an attempt to further study the graceful labeling of graphs formed
by joining two or more graphs, Hoede and Kuiper ([5], 1978)proved wheels
to be graceful and Frucht ([3], 1979) proved crowns are graceful. It has been
55
conjectured that cycles ([1], 1979) with an added chord are graceful, but this
has not been proved. Jungreis and Reid ([9], 1992) proved planar grids are
a-graceful, while Huang and Skiena ([7], 1994) proved cylindrical grids are
graceful if there are no odd cycles.
Remaining open questions are:
Ringels conjecture,
Ringel-Kotzig conjecture,
Kotzigs conjecture,
All lobsters are graceful,
All trees are graceful, and
Cycles with an added chord are graceful.
To prove Ringels conjecture or the Ringel-Kotzig conjecture we need an ap-
proach to prove all trees graceful as opposed to proving a class of trees graceful.
The typical induction argument used by the graph theorists will not work to
prove trees are graceful. Either a different induction approach is needed or an
approach which doesnt use induction since the technique applied to individual
classes of graphs do not lend themselves to the general case.
It appears some currently used approaches could be extended to
cover other cases. One promising approach might be attempting to apply
the components-moving tree of Wang, Ju, Lu, Zhang [8] to trees of diameter
4 no matter the parity of the degree of the center vertices of the components.
Another approach might be a merging of Huangs, Kotzigs, and Rosas [6] idea
of the un-join with induction. It is certainly easier to prove graphs are graceful
than to prove they are not graceful.
56
REFERENCES
[1] J.C. Bermond. Graceful graphs, radio antennae and french windmills.
Graph Theory and Combinatorics, 34:18-39, 1979.
[2] G.S. Bloom. A chronology of the Ringle-Kotzig Conjecture and the con-
tinuing quest to call all trees graceful. Annals of the New York Academy
of Science, pages 32-51, 1979.
[3] Roberto W. Frucht. Graceful numberings of wheels and related graphs.
Annals of the New York Academy of Science, 319:219-229, 1979.
[4] Roberto W. Frucht and Joseph A. Gallian. Labeling prisms. Ars Combi-
natoria, 26:69-82, 1988.
[5] C. Hoede and H. Kuiper. All wheels are graceful. Utilitas Mathematica,
14:311, 1978.
[6] C. Huang, A. Kotzig, and A. Rosa. Further results on tree labelings.
Utilitas Mathematica, 21:31-48, 1982.
[7] Jen-Hsin Huang and Steven S. Skiena. Gracefully labeling prisms. Ars
Combinatoria, 38:225-242, 1994.
[8] D.J. Jin and J.G. Wang. The gracefulness of the tree with a diameter four.
Acta Scientiarum Naturalium Universitatis Jilinensis, 1:17-22, 1993.
[9] Douglas S. Jungreis and Michael Reid. Labeling grids. Ars Combinatoria,
34:167-182, 1992.
[10] A. Kotzig. On certain vertex-valuations of finite graphs. Utilitas Mathe-
matica, 4:261-290, 1973.
[11] A. Rosa. On certain valuations of the vertices of a graph. Theory of
Graphs, pages 349-355, 1967.
[12] R.G. Stanton and C.R. Zarnke. Labeling of balanced trees. Utilitas Math-
ematica, VIIX:479-495, 1973.
57
[13] J.G. Wang, D.J. Ju, X.G. Lu, and D. Zhang. The gracefulness of a class of
lobster trees. Mathematical Computational Modelling, 20:105-110, 1994.
[14] Douglas B. West. Introduction to Graph Theroy. Prentice Hall, Inc.,
Upper Saddle River, NJ, 1996.
[15] Shi Lin Zhao. All trees of diameter four are graceful. Annals of the New
York Academy of Science, 576:700-706, 1989.
58
*
* |

PAGE 1
A SURVEY ON THE GRACEFUL LABELING OF GRAPHS by R. Lynn Watson B.S., Roanoke College, 1972 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 2000
PAGE 2
This thesis for the Master of Science degree by R. Lynn Watson has been approved by Richard Lundgren Sylvia Lu
PAGE 3
Watson, R. Lynn (M.S., Applied Mathematics) A Survey on the Graceful Labeling of Graphs Thesis directed by Professor Richard Lundgren ABSTRACT A graph G is said to be graceful if the numbers used to label its vertices are distinct values of the set {0, 1, ... m}, and the edge labels are the set {1, 2, ... m}, where the edge labels are the absolute value of the difference of the vertex values. Graceful labeling grew from Ringel's Conjecture, which states that for a given tree T with n vertices and n -1 edges, the edges of the complete graph I<2n-l can be partitioned into 2n-1 trees isomorphic to T. Ringel's Conjecture is one of the major unsolved problems of graph theory. The ex istence of a graceful labeling for a graph implies Ringel's Conjecture is true for that graph. It is this relationship between graceful labeling and Ringel's Conjecture that has created the interest and research in graceful labeling. This is a survey paper exploring the history of the prolonged and prolific interest in the graceful labeling of graphs, as well as the algorithms for gracefully labeling a variety of graphs, including paths, caterpillars, lobsters, k-ary trees, planar grids, cylindrical grids and balanced trees. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. Signed 111
PAGE 4
DEDICATION To my sons Brian Collison, Greg Collison, and Luke Egbert for their unending patience and support.
PAGE 5
ACKNOWLEDGEMENTS I would like to thank Rich Lundgren for his guidance and patience. I would als0 like to thank Stephen Billups and Sylvia Lu for their time and support in serving on my thesis committee.
PAGE 6
CONTENTS Figures Vll Chapter 1. Introduction 1 2. Paths ,.., ... I 3. Caterpillars 10 4. Grids ... 13 4.1 Planar Grids 14 4.2 Prisms 18 5. Coronas 22 s.1 \iVheels 22 5.2 Crowns 25 6. Cycles with a Chord 30 7. Trees ....... 34 7.1 Balanced Trees 35 7.2 K-ary Trees 38 7.3 Trees of Diameter four 41 7.4 Lobsters 51 8. Conclusion 55 References ... 57 Vl
PAGE 7
FIGURES Figure 1.1 A complete graph on 7 vertices partitioned into 7 trees with 3 edges 2 1.2 Gracefully labeled graph ..... 1.3 A gracefully labeled tree and I<2n-l 1.4 A gracefully labeled path 1.5 A caterpillar 2.1 A path .... 2.2 A gracefully labeled path Pn where n is even 2.3 A gracefully labeled path Pn where n is odd 2.4 An a-gracefully labeled path 3.1 A star ............ 3.2 A gracefully labeled caterpillar 3.3 A caterpillar which is gracefully labeled. 4.1 A grid on a plane ............ 4.2 C3DP2 -The Cartesian product of a 3-cycle and a path with two vertices 0 0 4.3 Graceful labeling J of P m 4.4 Labeling R( x) obtained from J 4.5 Graceful labeling K of P m ... 4.6 Labeling S(x) obtained from I< Vll 3 4 5 5 7 8 8 9 10 11 11 13 14 14 15 15 16
PAGE 8
4. 7 Graceful labeling J of ?5 . . 4.8 Labeling R(x) obtained from J 4.9 Graceful labeling I< of ?5 .. 4.10 Labeling S(x) obtain from I< 5.1 Corona C5 8 P2 ....... 5.2 Initial labeling of vertices in K1 8 Cs 5.3 Graceful labeling of K1 8 C8 . 5.4 Gracefully labeled graph K1 8 C9 5.5 The crown C5 8 K1 . . 5.6 Graceful labeling of Cs 8 K1 5. 7 Graceful labeling of C5 8 K1 5.8 Graceful labeling of C6 8 K1 5.9 Graceful labeling of C1 8 K1 6.1 Gracefully labeled C4 with chord 6.2 Gracefully labeled C6 with chord skipping one vertex. 6.3 Gracefully labeled C6 with a chord skipping two vertices 6.4 Gracefully labeled C14 with a chord skipping one vertex 6.5 Gracefully labeled C14 with a chord skipping two vertice s 6.6 Gracefully labeled C14 with a chord skipping three vertices 6.7 Gracefully labeled C14 with a chord skipping four vertices. 6.8 Gracefully labeled C14 with a chord skipping five vertices 16 17 17 18 22 23 24 25 26 27 27 28 29 31 31 31 31 32 32 32 33 6.9 Gracefully labeled C14 with a chord skipping six vertices 33 7.1 Attempting to gracefully label a graph after adding a pendant vertex 34 7.2 Construction of a balanced tree . . . . . . . . . 35 VI! I
PAGE 9
7.3 Gracefully labeled graphs S and T 0 0 36 7.4 Eight copies ofT which have been relabeled 37 7.5 Graceful labeling of graph U 38 7.6 Binary trees S and T 39 7.7 Relabeling copies of T 39 7.8 Gracefully labeled graph U 40 7.9 Relabeling the gracefully labeled third generation binary tree 40 7.10 Gracefully labeled binary tree of four generations 41 7.11 Gracefully labeled quaternary trees S and T . 41 7.12 Graceful labeling of the third generation quaternary graph U 42 7.13 Gracefully labeled graphs T1 and T2 . . 43 7.14 Gracefully labeled F, the uv-join of fr and h 43 7.15 A tree T of diameter 4 ............. 44 7.16 Gracefully labeled tree with n odd and Si even 49 7.17 Gracefully labeled tree of diameter 4 ... 53 7.18 Gracefully labeled lobster L of diameter 6 54 IX
PAGE 10
1. Introduction This is a survey paper of graceful labeling, which has been an area of interest in graph theory for almost forty years. The interest in graceful labeling grew from the discussion of the decomposition of a graph G or a partitioning of the edges E( G) into pairwise edge-disjoint subgraphs. A graph G with n vertices and m edges consists of a vertex set V(G) = {v1 ... ,vn} and an edge set E(G) = {e1 ... ,em}, where each edge consists of two vertices called its endpoints. Further a tree is a connected graph with no cycles and Kn is a complete graph of n vertices such that each of the vertices has an edge connecting it to every other vertex. In the decomposition of a graph the easiest case is to decompose the graph G into single edges. Soon more questions were asked. Can a graph G be decomposed into subgraphs isomorphic to a tree T of more than a single edge? If I E( G) I is a multiple of I E(T) I, can G be decomposed into isomorphic copies ofT? Are there some types of graphs which can be decomposed easier than others? Can we decompose regular graphs, complete graphs, trees or cycles? Are there any patterns? In 1963, Ringel [1] conjectured the following: Conjecture 1 LetT be a given tree with n vertices and n -1 edges; then the edges of K2n-l can be partitioned into 2n -1 trees isomorphic to T. Figure 1.1 shows the conjecture forT, a tree of 3 edges, and K7 Tree T has 4 vertices or n = 4. Per Conjecture 1 there are 7 distinct copies ofT in K7. It 1
PAGE 11
T Figure 1.1. A complete graph on 7 vertices partitioned into 7 trees with 3 edges is interesting to consider the number of edges in K2n-l relative to the number of edges in T. The number of edges in K2n-l is equivalent to the number of ways one can choose 2 from the group 2n -1 or (2n-l) (2n-1)(2n-2) ( )( ) 2 2n -1 n -1 2 Therefore, the number of distinct edges in K2n-l is always (2n 1) times E(T) 1. It remains to be proven that the partitioning results in trees isomorphic to T, but we know there exist the correct number of edges. In 1966 Rosa [11], reports Kotzig's stronger conjecture as stated here: Conjecture 2 Let T be a given tree with n vertices and n -1 edges, then the complete graph K2n-l can be cyclically partitioned into 2n -1 trees isomorphic toT. This cyclic partitioning is accomplished for an arbitrary T by identifying a suitable set of edges in K2n-l and rotating each node and edge from its orig inal position 2n -1 times. Conjecture 2 is referred to as the Ringel-Kotzig conjecture. The difference between Conjecture 2 and Conjecture 1 is the idea that the partitioning can be done cyclically, which is a stronger requirement. 2
PAGE 12
Certainly, if Conjecture 2 is true, then Conjecture 1 is also true. A graph G with m edges and n vertices can be labeled in such a way that the vertices are numbered and each edge is assigned a label equal to the absolute value of the difference of its vertex labels. A graph G is said to be graceful if the numbers used to label its vertices are distinct values of the set {0, 1, ... m }, and the edge labels are the set {1, 2, ... m }, where the edge labels are the absolute value of the difference of the vertex values. The function assigning values to each vertex v of G is denoted by f( v ). An example of a graceful labeling is in figure 1.2. It should be noted that these labelings are not usually unique. It should also be noted that the vertex labels are distinct values of the set {0, 1, 2, ... m }, not the complete set. It is possible to label the vertices in such a way as to produce two edges with the same label, which does not produce a graceful labeling. Figure 1.2. Gracefully labeled graph Alexander Rosa introduced the idea of graceful labeling in 1967 [11]. Rosa [11] then proved the following theorem. Theorem 1 If a tree T with n vertices and n -1 edges has a graceful labeling, then there exists a cyclic partitioning of the complete graph K2n-l into 2n-1 subgraphs isomorphic to T. 3
PAGE 13
------n,-----------------------------------------------------------------------------I I Figure 1.3. A gracefully labeled tree and I<2n-l Proof. View the vertices of I<2n-l as the congruence classes mod 2n 1. The displacement between two congruence classes is the number of unit moves needed to get from one to the other. The maximum displacement between two congruence classes mod 2n 1 is n 1. The edges of I<2n-J consist n 1 "displacement classes", each of size 2n 1. In other words one displacement class is all edges whose vertices are 1 unit apart and another displacement class is all edges whose vertices are 2 units apart so there are 4 displacement classes in the example (figure 1.3). From a graceful labeling of T, we define copies of T m K2n-l for 0 ::::; k ::; (2n-1) 1. In the kth copy, the vertices are k, ... k + (n-1) mod 2n 1, with k + i adjacent to k + j if and only if i is adjacent to j in the graceful labeling. The oth copy ofT looks just like the graceful labeling and has one edge with each displacement. If there is an edge from each displacement, there is an edge of each 'length' and the graceful labeling has been maintained. Moving to the next copy shifts each edge to the edge in its displacement class. Hence the 2n 1 copies of T cycle through the 2n 1 edges from each displacement class, without repetitions, and these 2n-1 copies ofT decompose Rosa's work and, m particular, this theorem launched the field of 4
PAGE 14
graceful labeling. Then Rosa made the following conjecture. Conjecture 3 All trees are graceful [10]. Ringel's Conjecture is one of the major unsolved problems of graph theory. The existence of a graceful labeling for a graph implies Ringel's Conjecture is true for that graph. It is this relationship between graceful labeling and Ringel's Conjecture that has created the interest and research in graceful labeling. Conjectures 1 and 2 remain two of the major unsolved problems in graph theory, which is the reason the topic of graceful labeling has such activity. A path is defined as a graph such that every vertex has degree at most 2 and exactly two vertices have degree 1. Rosa [11] proved that the simplest tree, a path, is graceful. Figure 1.4 shows an example of a gracefully labeled path. Figure 1.4. A gracefully labeled path A caterpillar (see figure 1.5) is defined as a graph such that deletion of every vertex of degree one results in a path. Figure 1. 5. A caterpillar Rosa [11] proved all caterpillars are graceful. Zhao [15] proved all trees of diameter four are graceful. An underlying idea in the graceful labeling of larger graphs is that of joining two or more gracefully labeled graphs and 5
PAGE 15
being able to gracefully label the resulting graph. This idea is explored in several chapters of this paper. In this survey paper we will explore algorithms for graphs that have been proven to be graceful and apply these algorithms to examples. The primary area of interest is trees, although we will also look at the graceful labeling of grids, crowns, coronas and cycles with a chord. The interest in graceful labeling of graphs other than trees is tangential to the graceful labeling of trees and the search for patterns leading to the graceful labeling of all trees. We must define a few more terms and the scope of this study before proceeding. A loop is an edge whose endpoints are equal. Parallel edges or multiple edges are edges whose endpoints are the same. A simple graph is a graph with no loops or parallel edges. A connected graph is a graph such that there exists an edge between any two subsets of the graph. In this paper only connected simple graphs are considered. Some related topics not discussed in this thesis are sequential labeling, harmonious labeling, Skolem graceful, edge graceful, and rotatable graceful. Graceful labeling grew from Ringel's and Kotzig's discussion of graph decomposition. Rosa proved K2n-l has a decomposition into 2n -1 copies T if T is a tree with n edges and can be gracefully labeled. This thesis explores the history of graceful labeling and discusses the results of graceful labeling different types of graphs. The algorithms for gracefully labeling a variety of graphs are presented for the general cases and demonstrated for specific cases. 6
PAGE 16
2. Paths A graph is called a path (see figure 2.1) if the degree d( v) of every vertex, v, is :::; 2 and there are no more than 2 endvertices [14]. An endvertex or leaf is a vertex of degree 1 Figure 2.1. A path Theorem 2 Every path is graceful [11]. Proof. We demonstrate an algorithm to gracefully label any path Pn with n vertices. In a path the number of edges is one less that the number of vertices or m = n -1. Labeling can begin at either end without loss of generality. The first vertex at one end is labeled 0, the adjacent vertex is labeled n -1, the next adjacent, non-labeled vertex is labeled 1, and we continue in this manner. Alternate vertices are incremently increasing by 1 while the remaining vertices are incremently decreasing by 1. Consider two cases where n O(mod 2) and n = 1(mod 2) shown in figures 2.2 and 2.3 respectively. In both cases k = l% J. For the even case the edge labels beginning with the leftmost edge in figure 2. 2 are I ( n -1) 0 I, I ( n -1) -1 I, I ( n -2) -1 I, ... I ( n -k) -( k -1) I= n-1, n-2, n-3, ... 1. In determining the last edge value recall k = l% J. For cases where n is even, k = l% J = % and ( n-k)-(k-1) = n-k-k + 1 = 1. It is easy to see this is a graceful labeling since all numbers between 1 and n -1 7
PAGE 17
or m are used in the edge labels. Similarly, when n is odd the edge values beginning on the left are n -1, n -2, n -3, ... 1. In evaluating the right most edge value, recall k = = when n is odd. Then n-k-k = n= 1. Again every value from 1 to n -1 or m is used. 0 ---tet----+ ----o-----.e-.. ---e ..... __ .. n-1 n-2 2 n-3 3 k:-1 n-k Figure 2.2. A gracefully labeled path Pn where n is even ...... ------e 0 n-1 n-2 2 n-3 n-k k Figure 2.3. A gracefully labeled path Pn where n is odd Rosa [13] also introduced a-graceful labeling, which is a stronger standard, and therefore fewer graphs are a-graceful. Graphs that are a-graceful are also graceful. A graceful graph G is said to be a-graceful if there exists a critical value a: such that for every edge (u, v), either f(u) ::; a: < f(v) or f( v) ::; a: < f( u). In each a-graceful graph, a: is a positive integer and the vertices are said to have an a-valuation. These a-graceful graphs must be bi-partite, which implies that no a-graceful graphs can have an odd cycle [3]. An example of a-graceful labeling is shown in figure 2.4, where a: = 3. Examine the vertex labels in the path shown in figure 2.4. Beginning at the left end of the path the first vertex is labeled 0 and alternate vertices to the right increase by 1. Call these vertex labels {0, 1, 2, 3} set A. While the left most vertex adjacent to vertex 0 is n -1 and each alternate vertex to the right decreases by 1. Call these vertex labels { 6, 5, 4} set B. Sets A and B appear to converge 8
PAGE 18
.. Figure 2.4. An a-gracefully labeled path to a value from the lower and upper sides respectively. In other words the values belonging to set A are less than or equal to some value and the values belonging to set B are greater that the same value. This is what is meant by a-graceful labeling, where a is this value to which is set A and B converge. 9
PAGE 19
3. Caterpillars Deleting every endvertex of a caterpillar results in a path. This path is called the spine of the caterpillar. What if the resulting path is one vertex or a point? Then the graph prior to deletion of end vertices is called a star as shown in figure 3.1. A star is a special case of caterpillar. Figure 3.1. A star Figure 3.2 shows the gracefully labeled caterpillar from figure 1.5. The first vertex on the spine is labeled 0 and the adjacent vertices are labeled {24, 23, 22, 21, 20} using the higher values on the leaf neighbors, so that 20 is the label for the next vertex on the spine and there are 4 leaf neighbors of vertex 0. Now the remaining non-labeled neighbors of 20 are labeled { 1, 2, 3, 4} with the lower values on the leaf neighbors and the value 4 on the next vertex on the spine. Continuing in this manner the caterpillar of 25 vertices is labeled. The edge values are {1, 2, 3, ... 24} and m = 24, while the vertex values are from the set {0, 1, 2, ... 24}. Therefore this labeling is a-graceful. Theorem 3 All caterpillars are a-graceful [11]. 10
PAGE 20
16 IS Figure 3.2. A gracefully labeled caterpillar Proof. We demonstrate an algorithm to a-gracefully label any cater pillar. Let vi represent the vertices on the spine of the caterpillar and N( vi) the neighborhood of vi, that is, the set of all vertices adjacent to vi, while IN( vi) I is the number of vertices which are adjacent to Vi. k; = { I N (vi) I -1, if i is the first or the last vertex of the spine I N( vi) I -2, otherwise Figure 3.3. A caterpillar which is gracefully labeled. (1) Begin by labeling the first vertex on the spine 0 (figure 3.3). Alternate vertices of this spine beginning with the first vertex are called odd. All other vertices on the spine are called even. (2) Leaf neighbors of 0 are labeled beginning with n -1 and gomg m descending order ending with n-k 1 where k1 = N( vo) -1. (3) The next vertex on the spine, a neighbor of 0, is labeled n-(k1 + 1). 11
PAGE 21
( 4) Leaf neighbors of this vertex n -( k1 + 1) are labeled 1 through k2 (5) Continue in this manner. The odd vertices on the spine and the leaf neighbors of the even vertices on the spine are labeled in increasing order, while the leaf neighbors of the the odd vertices on the spine and the even vertices on the spine are labeled in decreasing order. The last vertex on the spine is labeled n-(k1 + k3 + ... + ki-1 + r i l) if it is even. It is k2 + k4 + + ki_1 + i;l if odd. The last neighbor of this vertex is labeled k2+k4+ +ki-2+ki+ i;l or n-(k1 +k3+ +ki-2+ki+ lfJ) respectively. (6) a= min {x,y} where x =the label of last vertex on the spine and, { min{ labels of leaf neighbors }, y = max{ labels of leaf neighbors }, if x < labels of leaf neighbors if x > labels of leaf neighbors In the example in figure 3.2 a= min{9, 10, 11, 12, 13, 14, 15, 16} = 9.0 12
PAGE 22
4. Grids A grid is a graph defined as the Cartesian product of two graphs. Grids are not trees and not directly related to the proof of Ringel's conjecture (Conjecture 1). However, interesting work has been done in the area of gracefully labeling grids, as we show in this chapter. The Cartesian product GDH of graphs G and H whose vertex set is V( G) x V(H) can be defined as follows. Let u be a vertex in V(G) and v be a vertex in V(H). Then (u,v) is an element of GDH and (u,v) is adjacent to (u',v') if and only if (1) u = u' and edge vv' belongs to E(H) or (2) v = v' and edge uu' belongs to E(G) [14] (see figure 4.1). The grid shown is a planar grid P3DP5 where Pm is a path with m vertices. a3 b3 c3 d3 e3 a 2 b2 c2 d2 e2 a! bl cl dl el Figure 4.1. A grid on a plane Another type of grid is a cylindrical grid CmDPn as shown in figure 4.2, where Cm is a cycle of length m. Imagine a cylindrical grid as the grid from figure 4.1 on the curved surface of a cylinder. The last type of grid, CmDCn, is on a torus. Following are algorithms for gracefully labeling planar 13
PAGE 23
cl c2 L7 a! a2 G 0 H GDH Figure 4.2. C3DP2 -The Cartesian product of a 3-cycle and a path with two vertices and cylindrical grids respectively. 4.1 Planar Grids Theorem 4 The graph PmDPn has an a-valuation or a-graceful labeling [9]. Jungreis and Reid (9] developed the following algorithm Note: This algorithm assumes m ::; n. If m > n, find a graceful labeling for PnDPm and use the transpose of the resulting labeling as if it were a matrix. (1) Let J represent the graceful labeling of Pm (figure 4.3). -----<-------1t----4t-----a ..... -----0 m-1 m-2 2 k-1 m-k Figure 4.3. Graceful labeling J of Pm (2) Let x = k(2m -1) and R( x) be the labeling that results from adding (2mn -2m -n + 1) -x to the higher values in the J labeling and adding x to the lower values (figure 4.4), where i = 0, 1, 2, ... n;I. ( 3) Let [{ = ( m -1) -J represent another graceful labeling of P m (figure 4.5). This alternate labeling is also called the complement with respect tom-1. 14
PAGE 24
. . X 2mn-m-n-x x+l 2mn-m-n-1-x x+2 x+k-1 2mn-m-n-k+lx Figure 4.4. Labeling R( x) obtained from J (4) Let x = k(2m-1) +(1-m) and S(x) be the labeling obtained by adding (2mn-2m-n + 2)-x to the higher values in the f{ labeling and adding x to the lower values (figure 4.6), where k = 1, 2, ... The definition of x is different for the functions R and S. R(x) and S(x) are the foundation for the graceful labeling of the grid PmDPn. Each column of the grid is a copy of Pm and there are n columns. The first column is the (2k + l)st copy where k = 0. The labeling in that column and all odd numbered columns will be determined by the function R(k(2m-1)), where k = 0, 1, n;l. The labeling in even numbered columns or 2kth copies will be determined by S(k(2m1) + (1 m)), where k = 1, 2, The raised quantities st and th in the previous expressions are not exponents, but suffixes as in 1st or 5th.) This algorithm produces an a-graceful labeling [9). Examine the table of values below to see that the odd columns of the grid are labeled according to the function R( x) while the even columns are labeled using the function S ( x). The odd rows of the R(x) function begin with 0 and incremently increase. The even rows begin with the highest value in the grid and incremently decrease. For the S(x) function the odd rows begin with a higher value and decrease, -----i-----te.----ilt----ee ..... ----- m-1 0 m-2 m-3 m-k k-1 Figure 4.5. Graceful labeling I< of Pm 15
PAGE 25
....... ,___ __ ... 2mn-m-n+l-x 2mn-m-n-x x+l 2mn-m-n-l-x 2mn-m-n-k+2-x x+k-1 Figure 4.6. Labeling S(x) obtained from K while the even rows start with smaller values and increase. This means adjacent vertices are approaching a middle value from below and above. This middle value is a. 0 2mn-2m-n + 1 2m -1 ... 2mn-n + k-2km 2mn-m-n m 2mn-3m-n + 1 ... 2km-k-m + 1 1 2mn-2m-n 2m ... 2mn -n + k -2km -1 2mn-m-n-1 m+ 1 2mn-3m-n ... 2km-k-m + 2 2 2mn-2m-n -1 2m+ 1 ... 2mn -n + k -2km -2 p-1 2mn -2m -n -p + 2 2m+ p-2 ... 2mn -n + k -2km -p + 1 2mn -m n -p + 1 m+p-1 2mn -3m -n -p + 2 ... 2km -k -m + p -1 The following example illustrates the process for P5DP6 In P5DP6, m 5 and n = 6_ First, gracefully label P5 as shown in figure 4.7 0 4 3 2 Figure 4. 7. Graceful labeling J of P5 Next calculate 2mn-2m-n + 1-x and add the result to the higher labels of J and add x to the lower labels of J to obtain labeling R( x) (figure 4.8). 2mn-2m-n + 1-x = 2(5)(6)-2(5)-(6) + 1-x = 45-x Develop an altern ate graceful labeling K of P5 using K = ( m-1) 1, which is the complement with respect to m-1 (figure 4.9). 16
PAGE 26
X 49-x x+l 48-x x+2 Figure 4.8. Labeling R(x) obtained from J Now add 2mn-2m-n + 2-x to all higher values of labeling]{ and add x to all lower values of ]{ to obtain labeling S( x) (figure 4.10). 2mn-2m-n + 2-x = 2(5)(6)-2(5)-(6) + (2)-x = 46-x If k = 0, (2k + 1) = 1, use R(k(2rn-1)) = R(0(2(5)1)) = R(O). R(O) = 0, 49, 1, 48,2 If k = 1, (2k) = 2, use S(k(2m-1) +(1-m))= S(1(2(5)-1) + (1-5)) = S(5). 8(5) = 45,5,44,6,43 If k = 1, (2k + 1) = 3, use R(k(2m-1)) = R(1(9)) = R(9) R(9) = 9,40,10,39,11 If k = 2, (2k) = 4 use 5(k(2m-1) +(1-m))= 5(2(9)-4)) = 5(14) 5(14) = 36,14,35,15,34 If k = 2, (2k + 1) = 5 use R(k(2m-1)) = R(18) R(l8) = 18,31,19,30,20 If k = 3, (2k) = 6 use 5(k(2m-1) +(1-m))= 5(3(9)-4)) = 5(23) 5(23) = 27,23,26,24,25 The labels form the matrix shown below. Each value represents a vertex in the grid. Examination shows this is a gracefully labeled grid and 4 0 3 2 Figure 4.9. Gracefullabeling K of P5 17
PAGE 27
50x X 49x x+l 48-x fl Figure 4.10. Labeling S(x) obtain from K closer examination reveals that it is a-graceful where a = 24. 0 45 9 36 18 27 49 5 40 14 31 23 1 44 10 35 19 26 48 6 39 15 30 24 2 43 11 34 20 25 4.2 Prisms The prism (also called cylindrical grids) Pm,n is defined as the Cartesian product CmDPn where n 2 2 [7]. Jungreis and Reid (9] developed algorithms for the cases m = O(mod 4) for any nand m = 2(mod 4), n = O(mod 2). They have not developed an algorithm form= 2(mod 4) and n = 1(mod 2) or form 1(mod 2). Building on this work, Huang and Skiena [7] developed algorithms for all c ases where m O(mod 2) When m = 1(mod 2) and 3 ::; n ::; 12 they use these same algorithms for the first m-3 columns and use computers to produce tables for the values in the last two columns Frucht stated [3] that all prisms were graceful and he would so show in a later article, but so far, he has not shown this result. Frucht [4] proved that all prisms with n = 2 are graceful. Thus far, it has not been proven that all prisms with odd c y cles are graceful. 18
PAGE 28
Theorem 5 All prisms are graceful if they have no odd cycles [3]. The following examples use the algorithm given by Huang and Skiena. Graceful labeling of prisms with even cycles falls into two primary cases depending upon whether m is divisible by 4. CASE 1) When m = O(mod 4) or C4pDPn, use the following labeling. f(i,j) =(in+ lfJ)o(i + j + 1)+ ((2n -1)m-in+ J -lfJ-o(i + j) where it:{O, 1, 2, ... m-1} labels the column, jc::{O, 1, 2, ... n-1} labels the row, o(x) = x(mod 2), and each row in the matrix of values represents one copy of C4p When the parity i + j is odd, o(i + j) = 1 and o(i + j + 1) = 0, so that the first term in the labeling function J(i,j) = 0 and the value at this vertex is determined by the second term of the labeling function. When the parity of i + j is even, the opposite happens and the first term of J( i, j) determines the value. The table below shows the values for the prism C4DP5 where p = 1 and n = 5. 0 1 2 3 0 0 32 9 18 1 36 5 22 14 2 1 31 10 17 3 35 6 21 15 4 2 30 11 16 19
PAGE 29
CASE 2) When m = 2(mod 4), there are again two cases, depending on the parity of n. Part A will address the case where n O(mod 2) and Part B will deal with the case for n = l(mod 2). Part A) For m = 2(mod 4), m 6, n 4, and n = O(mod 2) or C4p+2DP29 where p 1, q 2 Huang and Skiena use a different presentation of Jungreis and Reid's algorithm which is shown here. J(i,j) =(in+ lfJ)o(i + j + 1)+ ((2n -1)m-in+ l J -lfJ-o(i + j) The example shown in the table below is for the prism C6DP4 where p = 1 and q = 2 or m = 6 and n = 4. 0 1 2 3 4 5 0 0 39 7 28 14 20 1 42 4 35 11 24 17 2 1 38 8 27 15 19 3 41 5 34 12 23 18 Part B) Form= 2(mod 4) and n = 1(mod 2) or C4p+2DP29+1 where p 1, q 1 the labeling is defined as f(i,j) =(in+ lfJ + + j + 1)+ ((2n-1)m-in+ l !:IfJltJ) o(j + 1) for i ::::; m -3. This labels the vertices in all of the columns except the last two. The labels for the vertices in the next to the last column are given by the following labeling: 20
PAGE 30
f(m-2,0) = H -n+2, f(m-2, 1) = H + 2n, where H = and f(m-2,j) = (H + 2nljt1 J) o(j) + (H + 4n + 2J) o(j + 1), for j 2. The labels for the vertices in the last column are defined as f(m-1, 0) = H-n + 1, f(m-1, n-1) = H + 3(n2-l), and f(m-1,j) = (H+ liJ)o(j)+ for 1 j n-2. Using the prism C6DP5 (p = 1 and q = 2) as an example, the resulting vertex labels are shown in the table below. 0 1 2 3 4 5 0 0 50 9 41 24 23 1 54 5 45 19 37 27 2 1 49 10 40 46 30 3 53 6 44 20 35 28 4 2 48 11 39 47 33 21
PAGE 31
5. Coronas Coronas are a class of graphs created by joining two or more graphs. The corona G1 8 G2 of two graphs G1 and G2 is the result when the two graphs are joined in the following way. Assuming G1 has p1 points, one copy of G1 is used and p1 copies of G2 are used. The ith point of G1 is joined to every vertex in theith copy of G2 [3] (figure 5.1). Figure 5.1. Corona C5 8 P2 5.1 Wheels The wheel is the corona K1 8 Cn where K1 is a graph of one vertex. Wheels can also be described as the result of adding a center to an n-gon where n 2:: 3 and making this center adjacent to every vertex in the n-gon by adding the appropriate edges [3] (see figure 5.2). Theorem 6 Wheels are graceful graphs [3]. In order to gracefully label wheels consider two cases n = O(mod 2) or n l(mod 2). 22
PAGE 32
CASE 1) n = O(mod 2) First number the vertices of the wheel so that the center of the wheel is v0 and the remaining vertices are given values v 1 v2, ... Vn sequentially. Now use the following algorithm to relabel the vertices and obtain a graceful labeling. 2n-i-1 if i=2,4,6, ... ,n-2 2 if i = n-1 if i = 0, 1,3,5, ... n-3 2n if i = n For n = 8 use the following example. First label the vertices vo, v 1 v2, ... vs as shown in figure 5.2. Figure 5.2. Initial labeling of vertices in I<1 8 Cs Per the algorithm v0 v1 v3 and v5 are relabeled 0, 1, 3, and 5 respectively. The vertex v8 is labeled 2n or 16 and v7 is labeled 2. Now the remaining even-numbered vertices v2 v4 and v6 are relabeled with the complement with 2n-1-i resulting in 13, 11, and 9 respectively (see figure 5.3). 23
PAGE 33
2 13 3 5 Figure 5.3. Graceful labeling of J*
*
PAGE 34
13 15 Figure 5.4. Gracefully labeled graph I<1 8 C9 5.2 Crowns A crown (figure 5.5) is a cycle Cn plus edges pendant at each vertex [1]. The notation for a crown is Cn 8 which is the reverse order of a wheel. Frucht showed that all crowns are graceful [3] by using four cases depending upon the parity of n (mod 4). CASE 1) If n = 0( mod 4) a graceful labeling for Cn 8 /{1 is obtained by using the following algorithm. First label the vertices of the cycle v1 v2 ... Vn in order and label the vertex pendant to V i by U i for i = 1, 2, ... n i-1, if i = 1 3, 5, ... ,%1 if i = % + 1, + 3, ... n-1 2n+1:_i, ifi=2,4,6, ... ,n and if i = 1, 2,3, ... ,% f n 1 n 2 1 2 = 2 + '2 + . n where n is the number of vertices in the cycle Thus the edges of the cycle are 25
PAGE 35
Figure 5.5. The crown C5 8 K1 (vi, v2), (v2, v3), ... (vn-1, vn), (vn, vr) and the edges joining Cn to the pendant points Ui are (ui, vi) An example for n = 8 is shown in figure 5.6. CASE 2) If n = 1 (mod 4), values for the vertices are given by and i-1, n-3, for odd i i-nr if iill. -2 2 + 1 'f 2 4 6 n-l n z, 1 z = , ... -2 -2n-i, l'f = nt3 n nll n -1 2 2 l 2 ... 2n-f(vi), 2n + 1 f(v;), 2n-2-f(vi), 2n -1 -f (Vi), "f 1 2 3 n-3 1 z= , ... ,-2 -if i -n-l 2 if i = nl 2 "f n n 1 z --2-, 2-, ... n. An example using this algorithm where n = 5 is shown in figure 5.7. CASE 3) When n = 2(mod 4), there exists a graceful labeling given by 26
PAGE 36
10 u I 16 14 12 Figure 5.6. Graceful labeling of Cs 8 K1 6 Figure 5. 7. Graceful labeling of C5 8 K1 27
PAGE 37
An example of using this algorithm to gracefully label a crown where n = 6 is shown in figure 5.8. 12 Figure 5.8. Graceful labeling of C6 8 K1 CASE 4) When n = 3(mod 4), a graceful labeling is determined by 28
PAGE 38
i-1, 'f 1 3 5 n-l 1 z = ' ... -21'f; = n+3 n+7 n+ll n 2 2 2 ... 2n + 1 -i, if i = 2, 4, 6, ... n-1 and 'f -1 2 3 n+l 1 Z, , ... ,-2 -'f n+3 n+5 1 -2-, -2-, ... n. An example of gracefully labeling a crown where n = 7 is pictured in figure 5.9. 12 10 Figure 5.9. Graceful labeling of C1 8 K1 29
PAGE 39
6. Cycles with a Chord A cycle with a chord is a cycle Ck with any two non-adjacent vertices joined. It has been conjectured that these graphs can be gracefully labeled [3], although it has not been proven. These graphs are another example of a class of graphs formed by joining two or more gracefully labeled graphs, where the first graph is a cycle and the second graph is a path of length one. I gracefully labeled graphs of this nature for 4 ::; k ::; 14 as shown below. There are always k + 1 edges and in labeling the vertices there are two numbers between 0 and k + 1 that are not used. A pattern for assigning values to the vertices was not found. In drawing these graphs the chord can be drawn from any vertex without affecting the labeling. Without loss of generality one vertex is selected as the beginning of the chord, then chords will be drawn to each of the remaining vertices. Due to symmetry it will be necessary to label only some of these graphs to find graceful labelings of all Ck with a chord. In the graph C4 we only need to consider one chord shown in figure 6.1. In the graph C6, there are only two configurations we need to consider as shown in figure 6.2 and 6.3. For C14 there are eleven possible chords and with symmetry it is sufficient to examine and label only six of them (see figures 6.4-6.9). 30
PAGE 40
0 5 4 Figure 6.1. Gracefully labeled C4 with chord 6 Figure 6.2. Gracefully labeled C6 with chord skipping one vertex. Figure 6.3. Gracefully labeled C6 with a chord skipping two vertices Figure 6.4. Gracefully labeled C14 with a chord skipping one vertex 31
PAGE 41
IJ Figure 6.5. Gracefully labeled C14 with a chord skipping two vertices Figure 6.6. Gracefully labeled 014 with a chord skipping three vertices 12 Figure 6. 7. Gracefully labeled C14 with a chord skipping four vertices 32
PAGE 42
12 Figure 6.8. Gracefully labeled C14 with a chord skipping five vertices II Figure 6.9. Gracefully labeled C14 with a chord skipping six vertices 33
PAGE 43
7. Trees A tree is defined as a connected graph with no cycles [14). While several classes of trees have been shown to be graceful, Ringel's Conjecture remains open. There are several problems in proving that all trees are graceful. First, there needs to be an approach encompassing all trees instead of proving a specific type of trees is graceful. Second, induction, which works well t o prove many characteristics of trees, hasn t worked to prove gracefulness. Induction has traditionally been used on trees in the following manner. Given that a tree of n vertices has characteristic b, delete a pendant vertex and assume the remaining tree has characteristic b. For induction to work we must be able to re-insert the pendant vertex anywhere and prove characteristic b exists in the resulting tree. In a-graceful labeling, and graceful labeling in general, the placement of the vertex is critical to maintaining the graph's gracefulness. Induction does not allow any assumptions about placement of the pendant vertex and therefore, this type of induction cannot be used to prove gracefulness of trees. 3 _L I I I 0 4 2 6 0 5 2 4 6 0 5 2 s S' S" Figure 7 .I. Attempting to gracefully label a graph after adding a pendant vertex 34
PAGE 44
In the following example shown in figure 7.1 graph S is 0:'-gracefully labeled. Graph S' and S" show how a pendant vertex can be added in two different ways. S' is still 0:'-gracefully labeled, while S" cannot be 0:'-gracefully labeled [2]. Possibly another approach using induction would work. In the following sections we discuss balanced trees, k-ary trees, trees of diameter four, and lobsters. 7.1 Balanced Trees A balanced tree is defined in either of two ways. In both cases begin with two trees S and T. To create the balanced tree attach a copy of T to every vertex in S [12]. Another way to create a balanced tree is to attach a copy ofT to every vertex in S except one [12]. The second type of balanced tree includes a special type of binary, ternary, and all k-ary trees. Figure 7.2 shows trees S and T with the resulting balanced tree U of the first type. y s T Figure 7.2. Construction of a balanced tree If trees S and T are gracefully labeled, then U can be gracefully labeled [12]. First, a fixed vertex in T is selected. This is the vertex that 35
PAGE 45
will attach to vertices in S and is circled in figure 7.3. Assume I V(S) I= k and vertices of S are labeled 0, 1, ... k -1. Make k copies of T labeled Ti, i = 0, 1, ... k-1. The fixed vertex inTi will be labeled in+ 1 where I V(T) I= n. 6 \/ s T Figure 7.3. Gracefully labeled graphs S and T I V(U) I= nk = 24 so that V(U) will be labeled 1 to nk. The remaining vertices ofT will be labeled in the following manner. The highest remaining values will be adjacent to the fixed vertex with lowest value, so that the fixed vertex T0 will be 1 and the remaining vertices in T0 will be labeled 24 and 23. The fixed vertex in T1 is labeled 4 while the remaining vertices in T1 will be labeled 21 and 20 since 21 and 20 are the highest remaining available values. Continuing this way vertices adjacent to T7 are labeled 2 and 3. See the values on the 8 copies ofT in figure 7.4. Proceed in the following manner [12]. First attach vertex 1 of T0 at the end of graphS and call this u1 as shown in figure 7.5. Next attach to neighbors of u1 the remaining Ti with maximum value on the fixed vertex and call this u22 Adjacent to u22 the remaining Ti with the minimum value on the fixed vertex and call this u4 Continue in this manner alternating the maximum and minimum values until all copies ofT are attached to a vertex inS. Notice that 36
PAGE 46
v v 4 7 10 v v v 13 16 19 22 Figure 7.4. Eight copies ofT which have been relabeled 37
PAGE 47
the vertices in this balanced tree are labeled 1 to n instead of 0 to n 1. This is caused by the notation used in Stanton's and Zarnke's algorithm and could be modified to be consistent with other authors. To achieve this modification, label the fixed vertices in instead of in+ 1 and let the labels of V(U) go from 0 to I V(U) I -1. 11 Figure 7. 5. Graceful labeling of graph U 7.2 K-ary Trees In the previous section the algorithm produces a gracefully labeled tree by joining the gracefully labeled graphs S and T. The algorithm gives no instruction for gracefully labeling the graphs S and T. In the case of balanced k-ary trees the algorithm both labels and constructs the tree. A k-ary tree is a rooted plane tree in which each vertex has no more than k children or edges. In a balanced k-ary tree each non-leaf has exactly k children and every child of the same generation has the same number of descendants. The binary tree and all k-ary trees are special cases of the balanced tree. In building a binary tree 38
PAGE 48
so that it falls within the definition of a balanced tree, notice that the fixed vertex is always the root of the initial tree. A A 2 3 2 3 s T Figure 7 .6. Binary trees S and T The algorithm [12] for the k-ary cases is different from the algorithm used for other balanced trees. We will illustrate the algorithm first with an example involving binary trees. Start with the binary trees Sand T which are a-gracefully labeled as shown in 7.6. Vertex 1 in T is the fixed vertex that attaches to the vertices in S while vertex 1 in S is the designated vertex that will not have a copy ofT attached. Let I V(T) I= n. Relabel two copies ofT using ( n + 1) -u shown in figure 7. 7 where u is the vertex label. T! Figure 7. 7. Relabeling copies of T Next add n + 1 to the values in the odd rows and add 1 to the values in the even rows of one copy of T. In the other copy add n + 1 to the even rows and 1 to the odd rows (figure 7 7). Now the fixed vertices in the copies 39
PAGE 49
ofT are attached to the end vertices of S resulting in the new graph U (figure 7.8). The remaining vertex of Sis labeled 1. 2 6 Figure 7 .8. Gracefully labeled graph U To continue the process for a fourth generation, the new graph U is relabeled using n + 1-u, where n =I V(U) I or 7. Add n + 1 or 8 to odd rows and add 1 to even rows in one copy of U, while in the other copy add 8 to the values in the even row and add 1 to the values in the odd rows (figure 7.9). M-.. Ax 3 2 fi s 6 ll 14 10 11 7 3 Figure 7. 9. Relabeling the gracefully labeled third generation binary tree The fixed vertex in U is the root and is attached to the end vertices in S resulting in a binary tree of four generations as in figure 7.10. Gracefully labeling a 4-ary or quaternary tree is the next example. As in the binary case, S and T are initially identical and labeled as shown in figure 7 .11. Using n + 1 -u or 6 to relabel T gives T' as shown in the same figure. Use the idea from labeling balanced graphs in general to determine the value to add to the odd and even rows in the four copies Ti. Calculate in + 1, 40
PAGE 50
15 13 14 10 II Figure 7.10. Gracefully labeled binary tree of four generations where i = 0, 1, ... n-1 to get {1, 6, 11, 16}. 2 3 4 5 s I 2 3 4 5 T 5 4 3 2 I T' Figure 7 .11. Gracefully labeled quaternary trees S and T Add 1, 6, 11,16 from this last calculation to the odd rows ofT1 T2, T3 and T4 respectively. In the even rows add to T1 T2 T3 and T4 respectively 16, 11, 6, and 1. The result is shown in figure 7.12. This pattern works for k-ary trees where k is even. When k is odd, the middle copy has the same value added to even and odd rows. 7.3 Trees of Diameter four It has been proven that all trees of diameter four are graceful [15]. Diameter is defined as the maximum distance between any two points in the graph. We start with a discussion of certain graceful trees, which will lead to an interesting result regarding lobsters. A lobster is a tree such that if all pendant vertices were deleted, the remaining tree would be a caterpillar, which we show in figure 1.5. Huang, Kotzig, and Rosa [6] proved the following Lemma, which 41
PAGE 51
Figure 7.12. Graceful labeling of the third generation quaternary graph U allows us to prove trees of diameter four are graceful. The uv-join of T1 and T2 denoted T1u uv T2 is formed by joining the graphs at u and v (vertex u is placed on vertex v) where utY(T1 ) and vt:V(T 2 ) and the new graph has one less vertex than I V(T1 + T2 ) 1Lemma 1 states that there exists a graceful labeling for the uv-join of T1 and T2 if either T1 or T2 is a-graceful and the remaining tree is graceful. Lemma 1 Let fi be an a-labeling of a tree T1 with JI(u) = 0 (where uc::V(TI)), and let /2 be agracefullabeling of a tree T2 with h(v) = 0 (where vt:V(T2)). Then there exists a graceful labeling of the tree T = T;" uv T2 [Note: If T2 is a-graceful, then the resulting graph T is a-graceful as well.] Define a labeling g of T by f;(z), if uV(TI)\{u}, JI(u):::;a, g(z) = f;*(z) + m, if zt: V ( T1) \ { u}, f1(u) >a, h(z) +a, if zt: V ( T2 ) \ { v}, a, if z = u 42
PAGE 52
where a is the critical value in the a-graceful labeling ofT1 J;(v) =I aj1(v) [, J;*(v) = nJI(v), m is the number of vertices in T2 and n is the number of vertices in T1 Wang Ju, Lu, and Zhang refer to J;(v) and J;*(v) as the inverse labelings of JI(v), while others use the term "complement with respect to a or n" respectively 0 19 n=4 m=20 Figure 7.13. Gracefully labeled graphs T1 and T2 Examine the gracefully labeled graphs T1 and T2 in figure 7.13. Following the algorithm, each vertex in the component from T2 will have its value increased by 1, which is the value of a from j1 In the component from T1 the vertices whose value is less than or equal to a will be relabeled with I a-JI(u) I= {0, 1, ... a}. Those vertices whose value is greater than a will be relabeled with n fi ( u) + m = { 1 + m, 2 + m, ... n (a + 1) + m}. These values are shown in the uv-join of T1 and T2 in figure 7.14. 10 22 0 20 Figure 7.14. Gracefully labeled F, the uv-join of j1 and fz 43
PAGE 53
Shi-Lin Zhao [15] showed that all trees of diameter four are graceful by developing an algorithm to gracefully label them. Trees of diameter four are a class of lobsters and an example Tis shown in figure 7.15. The approach Zhao uses is also used by Huang [6] in gracefully labeling certain trees of diameter four. The group of Wang, Ju, Lu, and Zhang uses a similar approach as a premise for the graceful labeling of a special class of lobsters. Wang also used this approach with Jin [8] to prove that all trees of diameter four are graceful. This topic has created a lot of interest and many articles. Figure 7.15. A tree T of diameter 4 Theorem 7 All trees of diameter 4 are graceful. [15] In figure 7.15 call Vi and its neighbors component i. Every tree of diameter 4 must be similar to the one in figure 7.15. That is, there will exist some vertex x that is adjacent to pendant vertices and to other vertices that are not pendant vertices. These vertices can be categorized into three sets. A= {u: d(x,u) = 1, where u is a pendant vertex ofT} 44
PAGE 54
B = { v : d(x v) = 1, where v is not a pendant vertex ofT} C = {v: d(x,v) = 2, where vis a pendant vertex ofT}, where d(u,v) is the distance from u to v. We now describe to to label the vertices in these sets to produce a graceful labeling of T. Part 1) If n is odd and A= 0, let n s =LSi, where Si =I N(vi) I -1, i=l { Si, = Si1, if Si is odd if si is even 1 ( n n-i ) D1(i) = 2 rEI 1) + 1) 1 ( n i-1 ) and D2(i) = 2 1) + 1) Let k = n;l and define the graceful labeling ofT as follows: J(x) = s + 2k + 2 (7.1) !(vi) = s + 2k + 2-i, i = 1, 2, ... k (7.2) f(vk+i) = k + 2-j,j = 1,2, ... ,k + 1. (7.3) 45
PAGE 55
Equation 7.I labels the center vertex x and equation 7.2 labels the vertices in set B for i = I, 2, ... k, while equation 7.3 labels the vertices in set B for i=k+I,k+2, ... k+j. Before exploring the labeling of the leaf vertices, we need to examine the notation used for a leaf vertex The notation vJ designates the Jth leaf neighbor of Vi in set B. To label the leaf neighbors of set B, that is set C, we consider four cases: (I) the leaf neighbor for j =I, 2, ... I), (2) the leaf neighbor for j = I)+ I, I)+ 2, ... siI, (3) the leaf neighbor for j = ,Si I, and ( 4) the leaf neighbor for j = Si. Case I) For j =I, 2, ... t(si -I) and i = I,2, ... ,n, if i k if i > k. (7.4) Case 2) For J = ... s-I and i =I, 2, ... n, and also for j = si -I when Si is odd, { D2(i) + i + k +I + jI), f(vj)= D1 ( i) -i + 3k + 2 + j t( s -I), if i k (7.5) if i > k. 46
PAGE 56
Case 3) For J = Si -1 and s1 is even, if i k (7.6) if i > k, Case 4) The labeling for the last vertex in each V i is defined by f( v!J in each of the four sub-cases listed below Sub-case 1: If each Si is odd fori = 1, 2, ... n, then if i k if i > k. Sub-case 2: If each Si is even for i = 1, 2, ... n then i { ( + i + k + 1, f( vs.) if i k if i > k. (7.7) (7.8) Sub-case 3: If s is even, but some S i in the set { s1 s2 . sn} are even and the others are odd, then if Si is odd order the Vi such that i = 1, 2, ... a, n-a+ 1 n-a+ 2, ... nand if Si is even order the V i such that i =a+ 1 a+2, ... n-a. This ordering of Vi puts the even Vi in the middle of the sequence and the odd Vi at the beginning or the end so that a is the value of the subscript for the odd S i preceding the first even Si, while n-a+ 1 is the value of the subscript for the first odd Si following the last even Si. Define for odd Si where i = 1 2 ... a n-a+ 1 n-a+ 2, ... n as in Case 1 and define for even Si where i =a+ 1, a+ 2, ... n-a as follows. 47
PAGE 57
i -{ f(vsJ+ i-k +a, where i =a+ 1, a+ 2, ... n-a. if i ::; k (7.9) if i > k. Sub-case 4: If s is odd, but some S i in the set { s1 s2 .. sn} are even and the others are odd, then if Si is odd order the Vi such that i = 1, 2, ... a, n-a, n-a+ 1, ... ,nand if Si is even order the Vi such that i =a+ 1, a+ 2, ... n-a -1. This ordering of Vi puts the even Vi in the middle of the sequence and the odd vi at the beginning or the end, while a is defined as in Sub-case 3. Define f( v!J for odd Si where i = 1, 2, ... a, n-a, n-a+ 1, .. n as in Case 1 and define f( v!J for even Si where i = a+ 1, a+ 2, ... n-a-1 as shown below. { 0)(s+1)+i+k-a, = where i =a+ 1 a+ 2, ... n-a-1. if i ::; k if i > k. (7.10) To apply these algorithms compare the value of j to Si. If j = Si, use the appropriate formula from equations 7. 7-7.10. If j = Si -1, use equations 7.6 for even Si and equations 7.5 for odd S i If Hsi -1) < j < Si -1, use equations 7.5 and if j ::; Hsi1), use equations 7.4. The proof that this algorithm does indeed produce a gracefully labeled graph is one of examining the edge values ofT. The algorithm only provides a graceful labeling for graphs of diameter four where n is odd and A= 0. If n is odd and A =J. 0, then the component T' ofT that includes vertex x and A is a-graceful since it is a caterpillar. T-T' is graceful from Part 1 and T must be graceful by Lemma 1. Part 2) If n is even, let T' be A and let T" be one component incident to x 48
PAGE 58
that does not include vertices of A, then T' U T" is a caterpillar and has an a-graceful labeling T T' T" is graceful by results in Part 1 and tree T is graceful by Lemma 1. We now demonstrate the algorithm by gracefully labeling the example in figure 7 17. There are 5 vertices in set B and each s i is even 10 17 n=5 k=2 s = 14 Figure 7 .16. Gracefully labeled tree with n odd and S i even Begin by calculating the graceful values for vertex x and set B. f(x) = s + 2k + 2 = 14 + 2(2) + 2 = 20 f(vi) = s + 2k + 2-i = 14 + 2(2) + 2-i results in 19 and 18 respectively, f( vk+i) = k + 2 -j = 2 + 2-j which results in 3, 2, and 1 respectively In order to gracefully label the vertices in set C we need to calculate D1 ( i) and D2(i). Since D1(i) is used only where i > k, find D1(3), D1(4) and DI(5) and similarly only find D2(1) and D2(2). To calculate D1(i) and D2(i) we need the values of Si and which are s 1 = 2, s2 = 4, s3 = 4, s 4 = 2, and s 5 = 2 = = = 1, and = 1 based on the previously shown definitions. DI(3) = 1) + 1) + 1) + (s;1)) = t(O + 0 + 0 + 1) = 1 49
PAGE 59
D1 ( 4) = ( ( -1) + ( -1)) = H 0 + 0) = 0 D1(S) = -1)) = 0 r=6 D2 ( 1) = ( ( -1) + 0) = H 0 + 0) = 0 D2(2) = + -1)) = HO + 0) = 0 To assign values to v} the next step is comparing the value of j to Si and determining which of the equations to use. Begin with the next to last vertex in each 8i and work to the first vertex. The last vertex in each 8i will be labeled using one of the 4 sub-cases. S I I I 1 h'l I I 3 1nce 8 1 = 8 4 = 8 5 = w 1 e 8 2 = 8 3 = for vi j = 1 and 8 1 -1 = 1 so that we use (equation 7.6) for assigning values to the first vertex in s1 ,84 and 8 5 and for assigning values to the third vertex in 82 and 8 3 f(vD = 1+0+2+1 = 4,f(vf) = 4-0-2+14 = 16,f(vr) = 5-0-2+14 = 17 and f( = 2 + 0 + 2 + 1 = 5 and f( vJ) = 3-1 -2 + 14 = 14. The second vertex of 8 2 and 8 3 will be labeled by the second set of equations (equation 7.5) because 1) < j < Si1. = 0 + 2 + 2 + 2 = 6 and = 1-3 + 3(2) + 3 = 7. Since j ::; ( -1) the value for the first vertex in 8 2 and s3 must be assigned using the first set of equations (equation 7.4) so that f(v?) = 14-20 + 2 + 1 = 15 and f(v?) = 14 + 3-1-2-1 = 13. This leaves the last vertex of each 8i to label, which will be done from equations in Sub-case 2 since the sum of Si is even and each 8i is even. = 7 + 1 + 2 + 1 = 11, f(vn = 7 + 2 + 2 + 1 = 12, = 7 + 3-2 = s, 50
PAGE 60
f(vi) = 7 + 4-2 = 9, = 7 +5-2= 10 7.4 Lobsters Lobsters are defined as trees that result in caterpillars when all pendant vertices are deleted. It has been conjectured that all lobsters are graceful. Wang, working with Jin, Lu, and Zhang, [8] showed gracefulness of a class of lobsters. We examine the results of this study and show an example. To do this Wang, Ju, Lu, and Zhang introduced definitions and lemmas regarding moving components of a graph. Definition Let u and v be two adjacent vertices of the tree T By deleting edge uv ofT, T turns into two smaller trees u(T) and v(T) These smaller trees are said to be components ofT, and v(T) is called a component incident to u. Lemma 2 Let T be a graceful tree, fits graceful value function, u and v two vertices of T, and u1 and u2 two pendant vertices adjacent to u. If f(ul) + j(u2) = f(u) + f(v), or 2f(ut) = f(u) + f(v), then the trees and T" = T -UU} + VU} are graceful trees with graceful value functionf. T' and T" are called components-moving trees ofT. 51
PAGE 61
Lemma 3 Let f be a graceful labeling of T(V; E), p =I V I; then (1) For any uvcE, we have l(uv) =I J(u)-f(v) 1=1 c/;p(J(u))-c/;p(J(v)) I where l( vu) is the edge label of T; (2) For every u1 u2 u, vc V(T), if f(ui) + j(u2) = f(u) + f(v), or 2f(ui) = f(u) + J(v), then or 2p(J(ui)) = c/;p(J(u)) + c/;p(J(v)), where c/;p(J) = pf(v), vcV(T) and f(v) is the graceful label of graph T. The authors refer to (!) as an inverse transformation. It is the same function used by Stanton and Zarnke and is called the "complement with respect to p". Lemma 2 states that the components-moving transformation maintains the gracefulness of the graph. Lemma 3 proves that the graph will still be graceful after applying the function P" Using these lemmas, a new class of lobsters with diameter greater than four can be gracefully labeled. Begin with a graph T that is a collection of star trees whose center vertices are all positive evens or positive odds. A star tree is made of a center vertex connected to every other vertex The star trees are joined by selecting a pendant vertex from each and sticking them together. Label the vertices by the algorithm described for caterpillars in section 3. Use the gracefully labeled 52
PAGE 62
graph T from the earlier example in figure 7.17. 10 --=--16 ___ _::_ __ t--17 n=5 k=2 s = 14 Figure 7.17. Gracefully labeled tree of diameter 4 First apply the function p, which will change the label at vertex x from 20 to 0 The label of 0 here is a requirement of Lemma 1. Now a path of length 1 can be joined to graph T at the newly labeled vertex 0 and the second vertex on the path will be labeled according to the algorithm given with Lemma 1 which is 20. Based on Lemma 2, components incident to 0 can be moved. Specifically, the components containing VI and v5 can be moved to the new vertex labeled 20 since VI and v5 are labeled 1 and 19 respectively and add to 20. This process will be repeated. First apply the function p, then add a path of length one and finally move the components incident to vertex 20, containing VIs and v2 to vertex 0. Then the two components incident to vertex 0, containing vi and v4 can be moved to vertex 21. The resulting gracefully labeled lobster shown in figure 7.18 has diameter six. 53
PAGE 63
9 /16 2 v4 21 10/17 vs 1 Figure 7.18. Gracefully labeled lobster L of diameter 6 54
PAGE 64
8. Conclusion The search for gracefully labeled graphs began in an effort to prove Ringle's Conjecture or Conjecture 1 ( cf. [1], 1963). Just three years later Kotzig developed the Ringel-Kotzig Conjecture (cf. [11), 1966). Rosa ([11], 1967) introduced the idea of labeling vertices of the graph as a way of approaching the proof of Ringle's conjecture. Graceful labeling and a-graceful labeling came from this study. Kotzig ([10), 1973) then conjectured that all trees are graceful and Rosa ( cf. [10), 1973) proved that Kotzig's Conjecture (Conjecture 3) implies Ringle's Conjecture. In an effort to prove trees graceful Rosa proved paths ([11), 1963) and caterpillars ([11], 1963) are graceful. Stanton and Zemke ([12], 1973) proved balanced trees formed from two trees are graceful. K-ary trees are a class of balanced trees proved graceful by Stanton and Zemke ([12], 1973). Lobsters are conjectured to be graceful ([6), 1982). Huang, Kotzig, and Rosa ( [6), 1982) proved that a gracefully labeled graph can be joined in a certain way to an a-gracefully labeled graph to produce a gracefully labeled graph. Zhao ([15), 1989)proved all trees of diameter four are graceful. Wang, Ju, Lu, Zhang ([13), 1994) proved lobsters that begin as diameter four and are changed by the components moving tree are graceful. In an attempt to further study the graceful labeling of graphs formed by joining two or more graphs, Hoede and Kuiper ([5), 1978)proved wheels to be graceful and Frucht ([3), 1979) proved crowns are graceful. It has been 55
PAGE 65
conjectured that cycles ([1], 1979) with an added chord are graceful, but this has not been proved. Jungreis and Reid ([9], 1992) proved planar grids are a-graceful, while Huang and Skiena ([7], 1994) proved cylindrical grids are graceful if there are no odd cycles. Remaining open questions are: Ringel's conjecture, Ringel-Kotzig conjecture, Kotzig's conjecture, All lobsters are graceful, All trees are graceful, and Cycles with an added chord are graceful. To prove Ringel's conjecture or the Ringel-Kotzig conjecture we need an ap proach to prove all trees graceful as opposed to proving a class of trees graceful. The typical induction argument used by the graph theorists will not work to prove trees are graceful. Either a different induction approach is needed or an approach which doesn't use induction since the technique applied to individual classes of graphs do not lend themselves to the general case. It appears some currently used approaches could be extended to cover other cases. One promising approach might be attempting to apply the components-moving tree of Wang, Ju, Lu Zhang [8) to trees of diameter 4 no matter the parity of the degree of the center vertices of the components. Another approach might be a merging of Huang's, Kotzig's, and Rosa's [6) idea of the uv-join with induction. It is certainly easier to prove graphs are graceful than to prove they are not graceful. 56
PAGE 66
REFERENCES [1] J. C. Bermond. Graceful graphs, radio antennae and french windmills. Graph Theory and Combinatorics, 34:18-39, 1979. [2] G.S. Bloom. A chronology of the Ringle-Kotzig Conjecture and the con tinuing quest to call all trees graceful. Annals of the New Y01k Academy of Science, pages 32-51, 1979. [3] Roberto W. Frucht. Graceful numberings of wheels and related graphs. Annals of the New York Academy of Science, 319:219-229, 1979 [4] Roberto W. Frucht and Joseph A. Gallian. Labeling prisms. Ars Combi natoria, 26:69-82, 1988. [5] C. Hoede and H. Kuiper. All wheels are graceful. Utilitas Mathematica, 14:311, 1978. [6] C. Huang, A. Kotzig, and A. Rosa. Further results on tree labelings. Utilitas Mathematica, 21:31-48, 1982. [7] Jen-Hsin Huang and Steven S. Skiena. Gracefully labeling prisms. Ars Combinatoria, 38:225-242, 1994. [8] D.J. Jin and J .G. Wang. The gracefulness of the tree with a diameterfour. Acta Scientiarum Naturalium Universitatis Jilinensis, 1:17-22, 1993. [9] Douglas S. Jungreis and Michael Reid. Labeling grids. A rs Combinatoria 34:167-182, 1992. [10) A. Kotzig. On certain vertex-valuations of finite graphs. Utilitas Mathe matica, 4:261-290, 1973. [11] A. Rosa. On certain valuations of the vertices of a graph. TheoTy of Gmphs, pages 349-355, 1967. [12] R.G. Stanton and C.R. Zarnke. Labeling of balanced trees. Utilitas Math ematica, VIIX:479-495, 1973. 57
PAGE 67
[13] J .G. Wang, D.J. Ju, X.G. Lu, and D. Zhang. The gracefulness of a class of lobster trees. Mathematical Computational Modelling, 20:105-110, 1994. [14] Douglas B. West. Introduction to Graph Theroy. Prentice Hall, Inc., Upper Saddle River, NJ, 1996. [15] Shi Lin Zhao. All trees of diameter four are graceful. Annals of the New York Academy of Science, 576:700-706, 1989. 58 __ ___!_j______
*
* |