Leitergraph

Datei:Ladder graphs.svg

Die Leitergraphen <math>L_1</math>, <math>L_2</math>, <math>L_3</math>, <math>L_4</math> und <math>L_5</math>

Ein Leitergraph () ist in der Graphentheorie eine Klasse von Graphen mit der Struktur einer Leiter. Ein Leitergraph besteht aus zwei linearen Graphen gleicher Länge (die Holme), wobei je zwei einander entsprechende Knoten durch eine Kante (die Sprossen) miteinander verbunden sind. Jeder Leitergraph ist das kartesische Produkt zweier linearer Graphen, von denen einer genau eine Kante hat, und damit ein spezieller Gittergraph.

Definition

Ein Leitergraph <math>L_n</math> ist ein ungerichteter Graph <math>(V,E)</math> bestehend aus den <math>2n</math> Knoten

<math>V=\{ v_1, \ldots , v_{2n} \}</math>

und den <math>3n-2</math> Kanten

<math>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 \}</math>.

Eigenschaften

Datei:Ladder graph L8 2COL.svg

2-Färbung eines Leitergraphen

Ein Leitergraph <math>L_n</math> ist das kartesische Produkt

<math>L_n = P_2 \times P_n</math>

der beiden linearen Graphen <math>P_2</math> und <math>P_n</math> und damit ein spezieller Gittergraph <math>G_{2,n}</math>.

Weitere Eigenschaften sind:

• Alle Leitergraphen sind zusammenhängend, planar und bipartit. Für <math>n \geq 2</math> 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 <math>L_n</math> beträgt jeweils <math>n</math>
• Die chromatische Zahl des Leitergraphen <math>L_n</math> ist zwei und sein chromatisches Polynom ist <math>(\lambda-1)\lambda(\lambda^2-3\lambda+3)^{n-1}</math>.
• Die Anzahl der perfekten Matchings in dem Leitergraphen <math>L_n</math> ist gleich der Fibonacci-Zahl <math>f_{n+1}</math>.<ref>Ralph Grimaldi: Fibonacci and Catalan Numbers: An Introduction. John Wiley & Sons, 2012, ISBN 1-118-15976-4, S. 64. </ref>

Zyklische Erweiterungen

Zwei Ansichten eines Möbius-Leitergraphen

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

<math>E' = E \cup \{ \{ v_1, v_{2n-1} \}, \{ v_2, v_{2n} \} \}</math>,

dann erhält man einen zyklischen Leitergraph () <math>CL_n</math>. Ein zyklischer Leitergraph ist das kartesische Produkt <math>P_2 \times C_n</math> eines linearen Graphen mit einem Kreisgraphen <math>C_n</math> und damit für <math>n \geq 2</math> 3-regulär. Zyklische Leitergraphen sind die Polyedergraphen von Prismen und werden daher auch Prismengraphen () genannt.

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

<math>E' = E \cup \{ \{ v_1, v_{2n} \}, \{ v_2, v_{2n-1} \} \}</math>,

erhält man als Graph einen sogenannten Möbiusleitergraph () <math>ML_n</math>, der an ein Möbiusband erinnert und ebenfalls 3-regulär ist. Möbiusleitergraphen sind für <math>n \geq 3</math> nicht mehr planar und weisen einige interessante graphentheoretische Eigenschaften auf.<ref>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. </ref>

Siehe auch

• Sterngraph

Weblinks

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

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

Einzelnachweise

<references />