6.3. Graceful graphs
A
graph G of size m is called graceful if it is possible to label
the vertices of G with distinct elements from the set in such a
way that
the induced edge labeling,
which prescribes the integer
to the edge
joining vertices labeled i and j, assigns the labels
to the edges of G.
Such labeling called graceful labeling.
Not
every graph is graceful. See or
.
The
gracefulness of a graph G with
and without
isolated vertices is the smallest positive integer k for which it is
possible to label the vertices of G with distinct elements from the set
in such a way
that distinct edges receive distinct labels.
Such vertex labelings always exist:
if we order to the label
.
-
For every graph G of order n and size m without
isolated vertices
.
- All connected graphs of order at most 4 are graceful.
- There are exactly three connected nongraceful graphs of order 5. In each case the gracefulness is one more than the size.
We return to the decompositions and give a constructive proof for the next theorem:
H-decomposable graph.
Proof.
Let be a graph without isolated vertices and
suppose that
.
Hence there exists a labeling of vertices of H so that distinct edges
are labeled differently and
.
We
now construct a regular H-decomposable graph G of order .
Let and arrange
these vertices cyclically in clockwise order about a regular p-gon.
Next we define a graph by
and
.
For , define
by cyclically rotating
through a clockwise angle of
radians. Therefore,
,
and
.
The process is completed by defining
The graph G is therefore decomposable
into the graphs , each of which is isomorphic to H, and G
is 2m-regular.
Theorem 6.7.
If G is a graceful graph of size m, then there exists a partition
of into two subsets
and
such that the
number of edges joining
and
is
.
Proof
Let a graceful labeling of G
given. Denote the set of vertices labeled with an even integer by and the set
of vertices labeled with an odd integer by
.
All edges labeled with an odd integer
must join a vertex of and a vertex of
.
Since there are edges, the result follows.
Theorem 6.8. If G is a graceful eulerian graph of size m, then
.
Proof.
Let be an eulerian circuit of G, and let a
gra-ceful labeling of G be given that assigns the integer
to
for
, where
if
. So, the label of the edge
is
. Observe that
for . Thus the sum of the label of the edges of G
is
that is the sum of the edge labels of G is even. However, the sum of the edge labels is
so is even.
Consequently, or
, which implies the statement.
Theorem 6.9.
The cycle is graceful iff
.
We saw before that the complete graphs and
are graceful. It
is easy to see that
is also graceful. The next result of Golomb
shows that there are no other graceful complete graphs.
Theorem 6.10. (Golomb, 1972): The complete graph is graceful iff
.