Ladder graph

A ladder graph (English ladder graph ) is in graph theory, a class of graphs with the structure of a ladder. A conductor graph is composed of two linear graph of the same length ( the beams ), wherein any two nodes corresponding to one another by an edge ( rungs ) are interconnected. Each conductor 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

And edges

Properties

A ladder graph is the Cartesian product

Of the two linear graphs and, thus, a special grid graph.

Other features are:

• All conductors are connected graphs, planar and bipartite. For all conductors graphs are cyclic and hamiltonian.
• Except for the four corner nodes with degree two, all nodes of a ladder graph on the degree three.
• The diameter and the number of the lead stability graphs of each
• The chromatic number of the ladder graphs is two and his chromatic polynomial.
• The number of perfect matchings in the ladder graph is equal to the Fibonacci number.

Cyclic extensions

In a graph manager also connected to each other by an additional edge of the first and the second last and the second and the last node, thus forming

Then we obtain a cyclic ladder graph (English circular ladder graph ). A cyclic ladder graph is the Cartesian product of a linear graph with a circle graph and thus for 3- regular. Cyclic ladder graphs are the Polyedergraphen of prisms and are therefore also referred to as prism graph ( english prism graphs ).

If the four nodes instead connected crosswise with each other, thus forming

Obtained as a graph called a Möbius ladder graph (English Möbius ladder graph ), which is reminiscent of a Möbius band and also 3 -regular is. Möbius ladder graphs are no longer planar and have some interesting graph-theoretic properties.