Mathematical Background

Definition of Gracefulness of a Tree

For introduction, we'll talk about the definition of a graceful tree.

An example of graceful tree

As you can see from above, this is a tree with 31 nodes. Its vertices are labelled from 0 to 30 without repetition or omission. This is called a labelling on vertices.

If you look at numbers beside each edge, you will find that it is the difference of labels of its two endpoints. This is called a labelling on edges induced by a labelling on vertices.

There are 30 edges on this tree. If we look carefully at labels on edges, we'll find that every number from 1 to 30 appears once and only once. A labelling on vertices that induce such a labelling on edges is called graceful labelling of this tree.

More generally, a tree with n vertices has n-1 edges. If a labelling on vertices, in which every number from 0 to n-1 appears once and only once, can induce a labelling on edges where every number from 1 to n-1 appears once and only once, this labelling on vertices is called a graceful labelling.

If a tree has at least one graceful labelling, it is called a graceful tree. By definition, the tree above is graceful.

This definition of gracefulness is restricted to trees. It can be extended to general simple graphs.

The notion of a graceful labelling was proposed by Rosa in 1967. At that time he named it "β-valuation". The name "graceful labelling" was proposed by Golomb in 1972.

Graceful Tree Conjecture

Graceful Tree Conjecture (Ringel-Kötzig Conjecture): Every tree is graceful.

This conjecture implies the Ringel Conjecture: the complete graph K(2n+1) can be decomposed into 2n+1 isomorphic trees, each containing n edges.

Up to now, we have not many idea about how to deal with this conjecture, and it has attracted many mathematicians to work on it. Kötzig once said that effort for proving this conjecture is a "disease".

But we still have obtained some incomplete results. We have now proved gracefulness for some special classes of trees. Take caterpillars as an example. For a tree, if after removing all its leaves the remain is a path, this tree is called a caterpillar. It's easy to design an algorithm to construct a graceful labelling for a caterpillar. So caterpillars are graceful, by definition.

There are many theoretical results like this for other special types of trees. A more general result is proved by P. HrnČiar and A.Haviar in 2001[1]. They have proved that every tree with diametre at most 5 is graceful. Here, the diametre of a tree is defined by the largest distance between two vertices of this tree, counted by number of edges between these two vertices.

There are mathematicians who tried to use computers for verification of this conjecture. In 1998, Aldred and McKay did a verification of this conjecture on trees with at most 27 vertices[2]. They use an algorithm combining hill-climbing search and tabu search.

The algorithm used by this project is greatly optimized for a better speed.

Number of Trees

Why do we need so much idle computational power for this verification?

Below is a list of number of trees with a certain number of vertices.

n	Trees with n vertices
1	1
2	1
3	1
4	2
5	3
6	6
7	11
8	23
9	47
10	106
11	235
12	551
13	1,301
14	3,159
15	7,741
16	19,320
17	48,629
18	123,867
19	317,955
20	823,065
21	2,144,505
22	5,623,756
23	14,828,074
24	39,299,897
25	104,636,890
26	279,793,450
27	751,065,460
28	2,023,443,032
29	5,469,566,585
30	14,830,871,802
31	40,330,829,030
32	109,972,410,221

We can see that the number of trees with n vertices grows exponentially with n. An empirical relation is O(2.6687^n). So computational power needed for verification also grows exponentially. That's why we need you!

Reference and Further Reading

An introduction of graceful labelling on wikipedia.

An introduction of graceful graph on Mathworld.

Joseph A. Gallian, "A Dynamic Survey of Graph Labeling." The Electronic Journal of Combinatorics 5 (1998). MR 1668059 PDF, updated in 2008. This is a dynamic survey of labellings on graphs, graceful labelling included.

[1] P. HrnČiar, A. Haviar, All trees of diameter five are graceful, Discrete Math. 233 (2001) 133-150
[2] Aldred, R. E. L. and McKay, B. "Graceful and Harmonious Labellings of Trees." Bull. Inst. Combin. Appl. 23, 69-72, 1998.

If you have any suggestion for this page, please feel free to mail them to projectgtv@gmail.com!

By FANG Wenjie(aka fwjmath)
Attribution-Noncommercial-No Derivative Works 2.5 China Mainland