Graceful lettering

A graceful labeling of a graph with edges is a labeling of the nodes with different numbers between 1 and , so that each edge receives a unique label. The labeling of an edge results from the difference between the labeling of its two end nodes. A graph for which such a label exists is called a graceful graph . If there is also a number so that one node of each edge is labeled with a number less than and the other with a number greater than or equal , then it is a bipartite label . ${\displaystyle e}$ ${\displaystyle e+1}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

The term graceful lettering goes back to Solomon W. Golomb . Alexander Rosa originally used the term β-rating in his 1967 paper on graph labels. He called bipartite labels α ratings.

One of the unsolved problems in mathematics is the graceful tree conjecture , according to which there is graceful lettering for all trees .

Graceful graph

Some classes of graph are known to be graceful. One example is the linear graph . A graceful lettering is created when the nodes are labeled with the numbers . ${\displaystyle 1,n,2,n-1,3,n-2,\ldots }$

The following drawing shows a corresponding graceful label for the linear graph with five nodes.

Graph decompositions

The starting point for the consideration of graceful graphs was the investigation of graph decompositions . A complete graph can be broken down cyclically into copies of a graceful graph with edges, see also the Ringel-Kotzig conjecture . ${\displaystyle K_{2m+1}}$ ${\displaystyle 2m+1}$ ${\displaystyle m}$

Individual evidence

1. ^ Virginia Vassilevska: Coding and Graceful Labeling of Trees. SURF 2001. PostScript
2. ↑ Alexander Rosa : On certain valuations of the vertices of a graph. In: Theory of Graphs. International Symposium. Théorie des graphes. Journées internationales d'étude. Rome, juillet 1966. Gordon and Breach, New York and Dunod Paris, 1967, pp. 349-355