Graceful labeling

A graceful labeling of a graph with edges is a labeling of the nodes with different numbers between 1 and so thus every edge is assigned a unique labels. The label of an edge is the difference of the labels of its two end nodes. A graph for which there exists such a labeling, graceful graph is called. Is there also a number, so that a node of each edge as and the other is a number greater than or equal to less labeled with a number, then it is a bipartite labeling.

The term graceful labeling goes back to Solomon W. Golomb. Originally used the name Alexander Pink β - Review published in his 1967 essay on the graph labels. He called Bipartite labels α reviews.

One of the unsolved problems of mathematics is the Graceful Tree Conjecture, according to which there is a graceful labeling for all trees.

Graceful graphs

Some classes of graphs, it is known that they are graceful. One example is the linear graph. A graceful labeling arises when the nodes are labeled with the numbers.

A graceful labeling for the corresponding linear graph with five nodes shown in the following drawing.

Graph decompositions

Starting point for the consideration of graceful graphs was the investigation of graph decompositions. A complete graph can be cyclic in copies of a graceful graph with edges disassemble, see also Ringel- Kotzig conjecture.