In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a graceful labeling of a graph with e edges is a labeling

Graph labeling

In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to the edges or vertices, or both, of a graph....

 of its vertices with distinct integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s between 0 and e inclusive, such that each edge is uniquely identified by the positive, or absolute difference

Absolute difference

The absolute difference of two real numbers x, y is given by |x − y|, the absolute value of their difference. It describes the distance on the real line between the points corresponding to x and y...

 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

Solomon W. Golomb

Solomon Wolf Golomb is an American mathematician and engineer and a professor of electrical engineering at the University of Southern California, best known to the general public and fans of mathematical games as the inventor of polyominoes, the inspiration for the computer game Tetris...

; this class of labelings was originally given the name β-labelings by Alex Rosa in a 1967 paper on graph labelings.

A major unproven conjecture

Unsolved problems in mathematics

This article lists some unsolved problems in mathematics. See individual articles for details and sources.- Millennium Prize Problems :Of the seven Millennium Prize Problems set by the Clay Mathematics Institute, six have yet to be solved:* P versus NP...

 in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel

Gerhard Ringel

Gerhard Ringel was a German mathematician who earned his Ph.D. from the University of Bonn in 1951...

 and Anton Kotzig

Anton Kotzig

Anton Kotzig was a Slovak–Canadian mathematician, expert in statistics, combinatorics and graph theory. The Ringel-Kotzig conjecture on graceful labeling of trees is named after him and Gerhard Ringel.- Biography :...

, 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".

Selected results

• In his original paper, Rosa proved that an Eulerian graph with number of edges m ≡ 1 (mod 4) or m ≡ 2 (mod 4) can't be graceful.
• Also in his original paper, Rosa proved that the cycle C_n is graceful if and only if n ≡ 0 (mod 4) or n ≡ 3 (mod 4).
• All path graph
  Path graph
  In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
  
  s and caterpillar graphs are graceful.
• All lobster graphs with a perfect matching are graceful.
• All trees with at most 27 vertices are graceful; this result was shown by Aldred and McKay in 1998 using a computer program. An extension of this (using a different computational method) up to trees with 35 vertices was claimed in 2010 by the Graceful Tree Verification Project, a distributed computing project led by Wenjie Fang.
• All wheel graph
  Wheel graph
  In the mathematical discipline of graph theory, a wheel graph Wn is a graph with n vertices, formed by connecting a single vertex to all vertices of an -cycle. The numerical notation for wheels is used inconsistently in the literature: some authors instead use n to refer to the length of the cycle,...
  
  s, web graphs, Helm graphs, gear graphs, and rectangular grids are graceful.
• All n-dimensional hypercube
  Hypercube
  In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...
  
  s are graceful.
• All simple graphs with four or fewer vertices are graceful. The only non-graceful simple graphs with five vertices are the 5-cycle
  Cycle graph
  In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
  
   (pentagon
  Pentagon
  In geometry, a pentagon is any five-sided polygon. A pentagon may be simple or self-intersecting. The sum of the internal angles in a simple pentagon is 540°. A pentagram is an example of a self-intersecting pentagon.- Regular pentagons :In a regular pentagon, all sides are equal in length and...
  
  ); the complete graph K₅; and the butterfly graph
  Butterfly graph
  In the mathematical field of graph theory, the butterfly graph is a planar undirected graph with 5 vertices and 6 edges...
  
  .

Additional reading

• (K.Eshghi) Introduction to Graceful Graphs, Sharif University of Technology, 2002.
• (U. N. Deshmukh and Vasanti N. Bhat-Nayak), New families of graceful banana trees - Proceedings Mathematical Sciences, 1996 - Springer