Kreisgraph

Ein Kreisgraph ${\displaystyle C_{n}}$ ist ein ungerichteter Graph ${\displaystyle (V,E)}$ bestehend aus den ${\displaystyle n}$ Knoten

${\displaystyle V=\{v_{1},\ldots ,v_{n}\}}$

und den ${\displaystyle n}$ Kanten

${\displaystyle E=\{\{v_{1},v_{2}\},\{v_{2},v_{3}\},\ldots ,\{v_{n-1},v_{n}\},\{v_{n},v_{1}\}\}}$ ,

wobei meist ${\displaystyle n\geq 3}$ angenommen wird. Ein Kreisgraph mit ${\displaystyle n}$ Knoten wird auch ${\displaystyle n}$ -Kreis oder ${\displaystyle n}$ -Zyklus genannt.

Im Folgenden werden nur Kreisgraphen bestehend aus mindestens drei Knoten betrachtet.

• Alle Kreisgraphen sind zusammenhängend, planar, zyklisch, eulersch und hamiltonsch.^[1]
• Alle Kreisgraphen sind 2-regulär, das heißt jeder Knoten hat den Grad zwei.^[2]
• Der Kantengraph des Kreisgraphen ${\displaystyle C_{n}}$ ist isomorph zu seinem Ausgangsgraph, also wieder ein Kreisgraph mit ${\displaystyle n}$ Knoten.^[3]
• Der Durchmesser und die Stabilitätszahl des Kreisgraphen ${\displaystyle C_{n}}$ beträgt ${\displaystyle \lfloor {\tfrac {n}{2}}\rfloor }$ .^[4]
• Die chromatische Zahl des Kreisgraphen ${\displaystyle C_{n}}$ ist zwei, wenn ${\displaystyle n}$ gerade ist und drei, wenn ${\displaystyle n}$ ungerade ist.^[5]
• Das chromatische Polynom des Kreisgraphen ${\displaystyle C_{n}}$ ist ${\displaystyle (-1)^{n}(\lambda -1)+(\lambda -1)^{n}}$ .^[6]
• Alle Kreisgraphen sind für ${\displaystyle n\geq 2}$ zueinander homöomorph.

Eigenschaften spezieller Kreisgraphen sind:

• Der Kreisgraph ${\displaystyle C_{3}}$ ist ein spezieller Dreiecksgraph.
• Der Kreisgraph ${\displaystyle C_{4}}$ ist ein spezieller Gittergraph.
• Der Kreisgraph ${\displaystyle C_{5}}$ ist der bis auf Isomorphie eindeutige selbstkomplementäre Graph mit 5 Knoten.
• Der Kreisgraph ${\displaystyle C_{6}}$ ist der kleinste reguläre Graph, der nicht stark regulär ist.

• Linearer Graph
• Sterngraph
• Leitergraph

• Peter Tittmann: Graphentheorie: Eine anwendungsorientierte Einführung. Hanser Verlag, 2003, ISBN 3-446-22343-6. 
• C. Vasudev: Graph theory with applications. New Age International, 2006, ISBN 81-224-1737-X. 
• Walter D. Wallis: A Beginner's Guide to Graph Theory. 2. Auflage. Springer, 2007, ISBN 0-8176-4484-9. 

• Eric W. Weisstein: Cycle Graph. In: MathWorld (englisch).