Magischer Graph

Graphentheorie, Teilgebiet der Mathematik

Magische Graphen sind in der Graphentheorie eine Graphenklasse mit speziellen Bewertungen von Ecken und Kanten. Das Gewicht einer Kante ist dabei gleich der Summe der Bewertungen der Anfangs-, Endecke und der Kante selbst. Sind alle Kantengewichte gleich, redet man von einem kantenmagischen Graphen. Das Gewicht einer Ecke ergibt sich als Summe der Eckenbewertung und der Bewertung jeder dort beginnenden Kante. Sind alle Eckengewichte gleich, so redet man von eckenmagischen Graphen. Graphen, die sowohl ecken- als auch kantenmagisch sind, werden total magische Graphen genannt.

Eckenmagische Graphen

Bearbeiten

Sei   ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung  .   bzw.   sind ecken-magisch, wenn eine Eckenkonstante   existiert, so dass für jede Ecke   gilt:

  (Eckengewicht)

Gewicht einer Ecke ergibt sich als Summe der Eckenbewertung und der Bewertung jeder dort beginnenden Kante.

Kantenmagische Graphen

Bearbeiten

Sei   ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung  .   bzw.   sind kanten-magisch, wenn eine Kantenkonstante   existiert, so dass für jede Kante   gilt:

  (Kantengewicht)

Man gewichtet eine Kante mit der Summe der Bewertungen der Anfangs- und Endecke und der Kante selbst.

Total magische Graphen

Bearbeiten

Sei   ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung  .   bzw.   sind total magisch, wenn eine Eckenkonstante   und eine Kantenkonstante   existiert, so dass   bzw.   sowohl ecken- als auch kantenmagisch ist.

Beispiele

Bearbeiten
  • Der triviale Graph   (Graph mit einer Ecke und keiner Kante) ist total magisch mit der Eckenkonstante  . Die Kantenkonstante ist diskutabel.
  • Der Kreisgraph   (Dreieck) ist total magisch.
  • Der lineare Graph   ist total magisch.
  •   und   sind die einzigen total magischen Sterne.
  • Der Graph   ist total magisch.

Literatur

Bearbeiten
  • Alison M. Marr, W. D. Wallis: Magic Graphs. 2. Auflage. Springer, 2012, ISBN 978-0-8176-8391-7.
  • A. Kotzig, A. Rosa: Magic valuations of finite graphs. In: Canad. Math. Bull., 13, 1970, S. 451–461
Bearbeiten