6.4. The Ruler Problem
The problem: For a given positive integer m, construct a ruler m units in length so that all integral distances from 1 to m can be measured and the ruler is marked at a minimum number of places.
In number theory, a restricted
difference basis (with respect to a positive integer) is a set such that every integer k with
can be represented in the form
.
We can realize the equivalency: a
graph G of size m has a graceful labeling if the vertices of G
can be labeled with the elements of a restricted difference basis
in such a way that for each integer k with , there is a unique pair of adjacent
vertices, labeled
and
, so that
.
A
connected graph G of order n and size m with is called
harmonious if there exists a labeling
of the vertices
of G with distinct elements
of
such that each
edge
of G is
labeled
- where the
addition is
- and the resulting edge labels are
distinct.
Such labeling is called a harmonious labeling.
If G
is a tree then exactly
two vertices are labeled the same; otherwise the definition is the same.
We
saw that is harmonious
but
is not. What is the situation in general?
Theorem 6.11. (Graham and Sloane, 1980): The cycle is harmoniuos iff n is odd.
Proof.
Assume first that n is odd and
let be a cycle of length n.
The labeling that assigns the label i is harmonious and hence
is harmonious if n
is odd. (see the picture for
.)
Assume now that is even and suppose, to the contrary, that
is harmonious.
Let . Suppose that the labeling that
assigns
the label
is harmonious.
Consequently, the integers are distinct and
.
Therefore, the edge labels are and
.
Let
The sum of the edge labels of is
.
Thus, ; and so, since
;
Hence , which is impossible.
Although there is some similarity between the results for graceful cycles and harmonious cycles, there is no such similarity for complete bipartite graphs:
Theorem 6.12. (Graham and Sloane 1980):
The complete bipartite graph is harmonious
iff
.
Proof.
The labeling that assigns the central
vertex of the label 0
and assigns the endvertices the labels
is harmonious. Consequently, every star is
harmonious.
It remains to show that no other complete graph is harmonious.
Suppose, to the contrary, that some
complete bipartite graph where
, is harmonious.
Let the partite sets of be
and
, whith
.
By assumption, there is a harmonious
labeling of suppose that
this labeling assigns the integers
to the vertices of
and
to the vertices of
.
This and
are disjoint subsets
of
and furthermore
.
Since for , we have
, it follows that
or, equivalently,
.
Hence, for some , it follows that
, and so
, which contradicts the fact that A
and B are disjoint.
We saw in Theorem 6.10 that
the complete graph is graceful iff
. Harmonious complete graphs are characterized in
exactly the same way:


Proof.
Use the definition: during the labelling we can use negative integers as well!




-
if k and n are
even, then let
;
-
if k is even and n
is odd, then let
;
-
if k is odd then let
.
- if k and n are or opposite parity, then -t is the repeated label.
For the given integer t, label
the vertex with
, where
This is a harmonious labelling of . So
is harmonious.
Graham-Sloane Conjecture: Every nontrivial tree is harmonious.