Graceful Labeling

In graph theory, a graceful labeling of a graph with e edges is a labeling of its vertices with some subset of the integers between 0 and e inclusive, such that no two vertices share a label, and such that each edge is uniquely identified by the positive, or absolute difference between its endpoints. A graph which admits a graceful labeling is called a graceful graph.

The name "graceful labeling" is due to Solomon W. Golomb; this class of labelings was originally given the name β-labelings by Alex Rosa in a 1967 paper on graph labelings.

A major unproven conjecture in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that all trees are graceful. The Ringel-Kotzig conjecture is also known as the "graceful labeling conjecture". Kotzig once called the effort to prove the conjecture a "disease".

Read more about Graceful LabelingSelected Results

Other articles related to "graceful labeling, graceful, labeling":

Graceful Labeling - Selected Results
... Eulerian graph with number of edges m ≡ 1 (mod 4) or m ≡ 2 (mod 4) can't be graceful ... his original paper, Rosa proved that the cycle Cn is graceful if and only if n ≡ 0 (mod 4) or n ≡ 3 (mod 4) ... All path graphs and caterpillar graphs are graceful ...
Graph Labeling - Special Cases - Graceful Labeling
... A graph is known as graceful when its vertices are labeled from 0 to, the size of the graph, and this labeling induces an edge labeling from 1 to ... Thus, a graph is graceful if and only if there exists an injection that induces a bijection from E to the positive integers up to ... paper, Rosa proved that all eulerian graphs with order equivalent to 1 or 2 (mod 4) are not graceful ...

Famous quotes containing the words labeling and/or graceful:

    Although adults have a role to play in teaching social skills to children, it is often best that they play it unobtrusively. In particular, adults must guard against embarrassing unskilled children by correcting them too publicly and against labeling children as shy in ways that may lead the children to see themselves in just that way.
    Zick Rubin (20th century)

    Personal size and mental sorrow have certainly no necessary proportions. A large bulky figure has a good a right to be in deep affliction, as the most graceful set of limbs in the world. But, fair or not fair, there are unbecoming conjunctions, which reason will pa tronize in vain,—which taste cannot tolerate,—which ridicule will seize.
    Jane Austen (1775–1817)