Graceful labeling
From Wikipedia, the free encyclopedia
In graph theory, a graceful labeling of a graph with n vertices and e edges is a labeling of its vertices with distinct integers between 0 and e inclusive, such that each edge is uniquely identified by the positive, or absolute difference between its endpoints.[1] 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.[2]
A major unproven conjecture in graph theory is the Ringel-Kotzig conjecture, which hypothesizes that all trees are graceful. (The Ringel-Kotzig conjecture is also known as "Von Koch's conjecture"[3] and the "graceful labeling conjecture".) Kotzig once called the effort to prove the conjecture a "disease".[4]
[edit] 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.[2]
- Also in 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.
- All lobster graphs with a perfect matching are graceful.[5]
- All trees with at most 27 vertices are graceful; this result was shown by Aldred and McKay using a computer program.[6][7]
- All wheel graphs, web graphs, Helm graphs, gear graphs, and rectangular grids are graceful.[6]
- All n-dimensional hypercubes are graceful.[8]
- All simple graphs with four or fewer vertices are graceful. The only non-graceful simple graphs with five vertices are the 5-cycle (pentagon); the complete graph K5; and the butterfly graph.[9]
[edit] See also
[edit] References
- ^ Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. PostScript
- ^ a b Alex Rosa, "On certain valuations of the vertices of a graph." Theory of Graphs (International Symposium, Rome, July 1966), Gordon and Breach, N.Y. and Dunod Paris. (1967) 349–355
- ^ http://www.hta-bi.bfh.ch/~hew/informatik3/prolog/p-99/
- ^ C. Huang, A. Kotzig, and A. Rosa, "Further results on tree labellings". Utilitas Mathematica, 21c (1982) 31–48; cited in Gallian, 1998
- ^ "Von Koch's conjecture", Usenet post to sci.math.research by Jim Nastos, 2003. [1]
- ^ a b Joseph A. Gallian, "A Dynamic Survey of Graph Labeling." The Electronic Journal of Combinatorics 5 (1998). MR1668059 PDF, updated 2008
- ^ R. E. L. Aldred, B. D. McKay, "Graceful and harmonious labellings of trees", Bulletin of the Institute of Combinatorics and Its Applications 23 (1998), 69–72 MR1621760
- ^ Anton Kotzig. "Decomposition of complete graphs into isomorphic cubes", Journal of Combinatoric Theory, Series B, 31 (1981) 292–296 MR0638285; cited in Gallian, 1998
- ^ Weisstein, Eric W., "Graceful graph" from MathWorld.
- (U. N. Deshmukh and Vasanti N. Bhat-Nayak), New families of graceful banana trees - Proceedings Mathematical Sciences, 1996 - Springer
