Graceful labeling

Graceful labeling

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.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 by Alex 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 and caterpillar graphs are graceful.
*All lobster graphs with a perfect 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]
*All wheel graphs, web graphs, Helm graphs, gear graphs, and rectangular grids are graceful.
*All "n"-dimensional hypercubes 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]
*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 "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.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Edge-graceful labeling — In graph theory, an edge graceful graph labeling is a type of graph labeling. This is a labeling for simple graphs , namely ones in which no two distinct edges connect the same two distinct vertices, no edge connects a vertex to itself, and the… …   Wikipedia

  • labeling — noun a) A set of labels applied to the various objects in a system. 4:00 (722) An upper bound for the number of graceful labelings of a path with n edges. Sylvia R. Naples, Bard College b) The introduction of a traceable chemical group (e.g.,… …   Wiktionary

  • Graph labeling — In the mathematical discipline of graph theory, a graph labeling is the assignment of labels traditionally represented with integers to the edges or vertices, or both, of a graph. The labeling strategy depends on the category of the labeling.… …   Wikipedia

  • Graziöse Beschriftung — Eine graziöse Beschriftung eines Graphen mit e Kanten ist eine Beschriftung der Knoten mit unterschiedlichen Zahlen zwischen 1 und e + 1, sodass dadurch jede Kanten eine eindeutige Beschriftungen erhält. Die Beschriftung einer Kante ergibt sich… …   Deutsch Wikipedia

  • Linearer Graph — Der lineare Graph P6. Ein linearer Graph oder Pfadgraph ist ein Graph, der nur aus einem Pfad besteht. Lineare Graphen sind einfache Beispiele für Bäume. Sie haben keine Verzweigungen, sodass die mittleren Knoten den Grad 2, und die Endknoten den …   Deutsch Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • 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, the six ones yet to be solved are:… …   Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • Problèmes non résolus en mathématiques — Ce qui suit est une liste de problèmes non résolus en mathématiques. Sommaire 1 Problèmes du prix du millénaire 2 Autres problèmes encore non résolus 2.1 Théorie des nombres 2.2 …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”