Ladder graph

The ladder graphs , , , and ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{3}}$ ${\displaystyle L_{4}}$ ${\displaystyle L_{5}}$

A ladder graph ( English ladder graph ) is in Graph theory , a class of graphs with the structure of a conductor . A ladder graph consists of two linear graphs of equal length (the stiles), where two corresponding nodes are connected by an edge (the rungs). Every ladder graph is the Cartesian product of two linear graphs, one of which has exactly one edge, and thus a special grid graph .

definition

A ladder graph is an undirected graph consisting of the nodes ${\displaystyle L_{n}}$ ${\displaystyle (V,E)}$ ${\displaystyle 2n}$

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

and the edges ${\displaystyle 3n-2}$

${\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\}}$.

properties

2 coloring of a ladder graph

A ladder graph is the Cartesian product ${\displaystyle L_{n}}$

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

the two linear graph and , thus, a special grid graph . ${\displaystyle P_{2}}$ ${\displaystyle P_{n}}$ ${\displaystyle G_{2,n}}$

Further properties are:

• All ladder graphs are contiguous , planar, and bipartite . For all ladder graphs are also cyclic and Hamiltonian . ${\displaystyle n\geq 2}$
• Except for the four corner nodes with degree two, all nodes of a ladder graph have degree three.
• The diameter and the stability number of the ladder graph are each ${\displaystyle L_{n}}$ ${\displaystyle n}$
• The ladder graph's chromatic number is two and its chromatic polynomial is . ${\displaystyle L_{n}}$ ${\displaystyle (\lambda -1)\lambda (\lambda ^{2}-3\lambda +3)^{n-1}}$
• The number of perfect matchings in the ladder graph is equal to the Fibonacci number . ${\displaystyle L_{n}}$ ${\displaystyle f_{n+1}}$

Cyclical extensions

Two views of a Möbius ladder graph

If, in a ladder graph, the first and the penultimate as well as the second and the last node are connected by an additional edge, one forms

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

then one obtains a cyclic ladder graph ( English circular ladder graph ) . A cyclic ladder graph is the Cartesian product of a linear graph with a circular graph and thus for 3-regular . Cyclic Head graphs are the Polyedergraphen of prisms and are therefore Prism graph ( English prism graphs called). ${\displaystyle CL_{n}}$ ${\displaystyle P_{2}\times C_{n}}$ ${\displaystyle C_{n}}$ ${\displaystyle n\geq 2}$

If the four nodes are instead connected crosswise, one forms

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

are obtained as a graph of a so-called Möbius ladder graph ( English Möbius ladder graph ) that binds to a Moebius strip remembered and also 3 is regular. Möbius ladder graphs are no longer planar and show some interesting graph-theoretical properties. ${\displaystyle ML_{n}}$ ${\displaystyle n\geq 3}$

See also

• Star graph

Web links

Commons : Ladder graphs  - collection of images, videos and audio files

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

Individual evidence

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