- Graceful labeling
In
graph theory , a graceful labeling of a graph with "n" vertices and "e" edges is a labeling of its vertices with distinctinteger s between 0 and "e" inclusive, such that each edge is uniquely identified by the positive, or absolute difference between its endpoints.Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. [http://www.cs.cmu.edu/~virgi/final1.ps PostScript] ] 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 byAlex Rosa in a 1967 paper on graph labelings.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]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" [http://www.hta-bi.bfh.ch/~hew/informatik3/prolog/p-99/] and the "graceful labeling conjecture".) Kotzig once called the effort to prove the conjecture a "disease".C. Huang, A. Kotzig, and A. Rosa, "Further results on tree labellings". "Utilitas Mathematica", 21c (1982) 31–48; cited in Gallian, 1998]
elected results
*In his original paper, Rosa proved that no
Eulerian graph with order equivalent to 1 or 2 (mod 4) is graceful.
*All paths andcaterpillar graph s are graceful.
*Alllobster graph s with aperfect matching are graceful."Von Koch's conjecture",Usenet post to sci.math.research by Jim Nastos, 2003. [http://groups.google.com/groups?selm=Pine.LNX.4.44.0303310019440.1408-100000@eva117.cs.ualberta.ca] ]
*All trees with at most 27 vertices are graceful; this result was shown by Aldred and McKay using a computer program. Joseph A. Gallian, "A Dynamic Survey of Graph Labeling." The Electronic Journal of Combinatorics 5 (1998). MathSciNet|id=1668059 [http://www.combinatorics.org/Surveys/ds6.pdf 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 MathSciNet|id=1621760]
*Allwheel graph s,web graph s,Helm graph s,gear graph s, and rectangular grids are graceful.
*All "n"-dimensionalhypercube s are graceful.Anton Kotzig. "Decomposition of complete graphs into isomorphic cubes", "Journal of Combinatoric Theory", Series B, 31 (1981) 292–296 MathSciNet |id=0638285; cited in Gallian, 1998]
*Allsimple graph s with four or fewer vertices are graceful. The only non-graceful simple graphs with five vertices are the 5-cycle (pentagon ); the complete graph "K"5; and a "bow-tie" graph on five vertices, consisting of two triangles joined at one vertex.mathworld|title=Graceful graph|urlname=GracefulGraph]ee also
*
Edge-graceful labeling
*List of conjectures References
Wikimedia Foundation. 2010.