Graziöse Beschriftung

Eine graziöse Beschriftung eines Graphen mit Kanten ist eine Beschriftung der Knoten mit unterschiedlichen Zahlen zwischen 1 und , sodass dadurch jede Kante eine eindeutige Beschriftungen erhält. Die Beschriftung einer Kante ergibt sich als Differenz der Beschriftungen ihrer beiden Endknoten.[1] Ein Graph, für den eine solche Beschriftung existiert, wird graziöser Graph genannt. Gibt es zusätzlich eine Zahl , sodass ein Knoten einer jeden Kante mit einer Zahl kleiner als und der andere mit einer Zahl größer oder gleich beschriftet ist, dann handelt es sich um eine bipartite Beschriftung.

Die Bezeichnung graziöse Beschriftung g​eht zurück a​uf Solomon W. Golomb. Ursprünglich verwendete Alexander Rosa d​ie Bezeichnung β-Bewertung i​n seinem 1967 veröffentlichten Aufsatz über Graphenbeschriftungen. Bipartite Beschriftungen nannte e​r α-Bewertungen.[2]

Eines d​er ungelösten Probleme d​er Mathematik i​st die Graziöser-Baum-Vermutung, d​er zufolge e​s für a​lle Bäume e​ine graziöse Beschriftung gibt.

Graziöse Graphen

Von einigen Klassen von Graphen ist bekannt, dass sie graziös sind. Ein Beispiel sind die linearen Graphen. Eine graziöse Beschriftung entsteht, wenn deren Knoten mit den Zahlen beschriftet werden.

Eine entsprechende graziöse Beschriftung für d​en linearen Graphen m​it fünf Knoten z​eigt die folgende Zeichnung.

Graphzerlegungen

Ausgangspunkt für die Betrachtung graziöser Graphen war die Untersuchung von Graphzerlegungen. Ein vollständiger Graph lässt sich zyklisch in Kopien eines graziösen Graphen mit Kanten zerlegen, siehe dazu auch Ringel-Kotzig-Vermutung.

Einzelnachweise
  1. Virginia Vassilevska: Coding and Graceful Labeling of trees. SURF 2001. PostScript
  2. Alexander Rosa: On certain valuations of the vertices of a graph. In: Theory of Graphs. International Symposium. Théorie des graphes. Journées internationales d'étude. Rome, juillet 1966. Gordon and Breach, New York und Dunod Paris, 1967, S. 349–355
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.