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:

Theorem 6.13. The complete graph  is harmonious iff .

 

 

Theorem 6.14. Every nontrivial path is harmonious.

 

Proof.

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

Let , where . If n is even, write ; while if n is odd, write .
  • 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.