Magischer Graph

Sei ${\displaystyle G=(E,K)}$ ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung ${\displaystyle \lambda :E\cup K\to \{1,2,...,|E|+|K|\}}$. ${\displaystyle G}$ bzw. ${\displaystyle \lambda }$ sind ecken-magisch, wenn eine Eckenkonstante ${\displaystyle h\in \mathbb {N} }$ existiert, so dass für jede Ecke ${\displaystyle e\in E}$ gilt:

${\displaystyle wt(e):=\lambda (e)+\sum _{eb\in K}\lambda (eb)=h}$ (Eckengewicht)

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

Sei ${\displaystyle G=(E,K)}$ ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung ${\displaystyle \lambda :E\cup K\to \{1,2,...,|E|+|K|\}}$. ${\displaystyle G}$ bzw. ${\displaystyle \lambda }$ sind kanten-magisch, wenn eine Kantenkonstante ${\displaystyle k\in \mathbb {N} }$ existiert, so dass für jede Kante ${\displaystyle ab\in K}$ gilt:

${\displaystyle wt(ab):=\lambda (a)+\lambda (ab)+\lambda (b)=k}$ (Kantengewicht)

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

Sei ${\displaystyle G=(E,K)}$ ein endlicher einfacher ungerichteter Graph mit einer totalen Bewertung ${\displaystyle \lambda :E\cup K\to \{1,2,...,|E|+|K|\}}$. ${\displaystyle G}$ bzw. ${\displaystyle \lambda }$ sind total magisch, wenn eine Eckenkonstante ${\displaystyle h\in \mathbb {N} }$ und eine Kantenkonstante ${\displaystyle k\in \mathbb {N} }$ existiert, so dass ${\displaystyle G}$ bzw. ${\displaystyle \lambda }$ sowohl ecken- als auch kantenmagisch ist.

• Der triviale Graph ${\displaystyle K_{1}}$ (Graph mit einer Ecke und keiner Kante) ist total magisch mit der Eckenkonstante ${\displaystyle 1}$. Die Kantenkonstante ist diskutabel.
• Der Kreisgraph ${\displaystyle C_{3}}$ (Dreieck) ist total magisch.
• Der lineare Graph ${\displaystyle P_{3}}$ ist total magisch.
• ${\displaystyle P_{3}}$ und ${\displaystyle K_{1}}$ sind die einzigen total magischen Sterne.
• Der Graph ${\displaystyle K_{1}\cup P_{3}}$ ist total magisch.

• 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

• Eric W. Weisstein: Magic graph. In: MathWorld (englisch).
• Totally magic graphs