Importance: High ✭✭✭
Subject: Graph Theory
» Coloring
» » Labeling
Recomm. for undergrads: no
Posted by: kintali
on: July 13th, 2007
Conjecture   All trees are graceful

Label the vertices of a simple undirected graph $ G(V,E) $ (where $ |V| = n $ and $ |E| = m $) with integers from $ 0 $ to $ m $. Now label each edge with absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labelled $ 1 $ through $ m $ inclusive (with no number repeated).

A graph is called graceful if it has at least one such labeling. This labeling was originally introduced in 1967 by Rosa. The name graceful labeling was coined later by Golomb.

Gracefully labeled graphs serve as models in a wide range of applications including coding theory and communication network addressing.

The graceful labeling problem is to determine which graphs are graceful. It is conjectured (by Kotzig, Ringel and Rosa) that all trees are graceful.

Despite numerous (more than 200) publications on graceful labeling for over three decades, only a very restricted classes of trees (and also of some other graphs) have been shown to be graceful. These restricted classes include paths, stars, complete bipartite graphs, prism graphs, wheel graphs, caterpillar graphs, olive trees, and symmetrical trees.


* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.
More information about formatting options