Harmonious Trees/en

Aus Rechenkraft
Zur Navigation springen Zur Suche springen
Languages Languages

Deutsch ja.gif   Deutsch •  Deutsch nein.gif   English

Harmonious Tree Example (n=6)

In 1980, Graham and Sloane first introduced the notion of harmonious labelling on general graphs. It is a labelling scheme related to additive base. Basically, for a graph with e edges, a harmonious labelling is a labelling such that every node receives a different label that makes the sum modulo e of adjacent nodes runs from 0 through e - 1. This is not a trivial labeling, in the sense that not all graphs have a harmonious labelling. If a graph has a harmonious labelling, we say that it is harmonious.

Graham and Sloane proposed the following conjecture: Every tree is harmonious. Equivalently speaking, they conjectured that for every tree with n nodes, we can label them from 0 to n - 1 without repetition, such that the sum modulo (n - 1) of two adjacent nodes runs from 0 through n - 2.

According to Gallian's dynamic survey on graph labelling, there are few results on harmonious trees. Graham and Sloane proved that caterpillars are harmonious. Aldred and McKay used a computer program to verify that all trees with at most 26 nodes are harmonious. Recently, Fang proposed a new algorithm and pushed the verification to trees with at most 31 nodes. A distributed version of this algorithm is used in this subproject.

In this subproject, we aim to verify if trees with limited size are all harmonious. If they are all harmonious, it will confirm our faith in this conjecture. Otherwise, if a counter-example is found, it will immediately disprove the conjecture, therefore disprove a lasting open problem in graph theory.