Leitergraph

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

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

und den ${\displaystyle 3n-2}$  Kanten

${\displaystyle E=\{\{v_{i},v_{i+1}\}\mid i=1,3,\ldots ,2n-1\}\cup \{\{v_{i},v_{i+2}\}\mid i=1,2,\ldots ,2n-2\}}$ .

 

Ein Leitergraph ${\displaystyle L_{n}}$  ist das kartesische Produkt

${\displaystyle L_{n}=P_{2}\times P_{n}}$ 

der beiden linearen Graphen ${\displaystyle P_{2}}$  und ${\displaystyle P_{n}}$  und damit ein spezieller Gittergraph ${\displaystyle G_{2,n}}$ .

Weitere Eigenschaften sind:

• Alle Leitergraphen sind zusammenhängend, planar und bipartit. Für ${\displaystyle n\geq 2}$  sind alle Leitergraphen auch zyklisch und hamiltonsch.
• Bis auf die vier Eckknoten mit Grad zwei weisen alle Knoten eines Leitergraphen den Grad drei auf.
• Der Durchmesser und die Stabilitätszahl des Leitergraphen ${\displaystyle L_{n}}$  beträgt jeweils ${\displaystyle n}$ 
• Die chromatische Zahl des Leitergraphen ${\displaystyle L_{n}}$  ist zwei und sein chromatisches Polynom ist ${\displaystyle (\lambda -1)\lambda (\lambda ^{2}-3\lambda +3)^{n-1}}$ .
• Die Anzahl der perfekten Matchings in dem Leitergraphen ${\displaystyle L_{n}}$  ist gleich der Fibonacci-Zahl ${\displaystyle f_{n+1}}$ .^[1]

 

Werden in einem Leitergraphen zudem der erste und der vorletzte sowie der zweite und der letzte Knoten jeweils durch eine zusätzliche Kante miteinander verbunden, bildet man also

${\displaystyle E'=E\cup \{\{v_{1},v_{2n-1}\},\{v_{2},v_{2n}\}\}}$ ,

dann erhält man einen zyklischen Leitergraph (englisch circular ladder graph) ${\displaystyle CL_{n}}$ . Ein zyklischer Leitergraph ist das kartesische Produkt ${\displaystyle P_{2}\times C_{n}}$  eines linearen Graphen mit einem Kreisgraphen ${\displaystyle C_{n}}$  und damit für ${\displaystyle n\geq 2}$  3-regulär. Zyklische Leitergraphen sind die Polyedergraphen von Prismen und werden daher auch Prismengraphen (englisch prism graphs) genannt.

Werden die vier Knoten stattdessen kreuzweise miteinander verbunden, bildet man also

${\displaystyle E'=E\cup \{\{v_{1},v_{2n}\},\{v_{2},v_{2n-1}\}\}}$ ,

erhält man als Graph einen sogenannten Möbiusleitergraph (englisch Möbius ladder graph) ${\displaystyle ML_{n}}$ , der an ein Möbiusband erinnert und ebenfalls 3-regulär ist. Möbiusleitergraphen sind für ${\displaystyle n\geq 3}$  nicht mehr planar und weisen einige interessante graphentheoretische Eigenschaften auf.^[2]

• Sterngraph

 

Commons: Ladder graphs – Sammlung von Bildern, Videos und Audiodateien

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

1. ↑ Ralph Grimaldi: Fibonacci and Catalan Numbers: An Introduction. John Wiley & Sons, 2012, ISBN 1-118-15976-4, S. 64. 
2. ↑ Jonathan L. Gross: Combinatorial Methods With Computer Applications (= Discrete Mathematics and its Applications. Band 54). CRC Press, 2008, ISBN 1-58488-743-5, S. 376–377.