Ladder graph
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
and the edges
- .
properties
A ladder graph is the Cartesian product
the two linear graph and , thus, a special grid graph .
Further properties are:
- All ladder graphs are contiguous , planar, and bipartite . For all ladder graphs are also cyclic and Hamiltonian .
- 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
- The ladder graph's chromatic number is two and its chromatic polynomial is .
- The number of perfect matchings in the ladder graph is equal to the Fibonacci number .
Cyclical extensions
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
- ,
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).
If the four nodes are instead connected crosswise, one forms
- ,
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.
See also
Web links
- Eric W. Weisstein : Ladder Graph . In: MathWorld (English).
Individual evidence
- ^ Ralph Grimaldi: Fibonacci and Catalan Numbers: An Introduction . John Wiley & Sons, 2012, ISBN 1-118-15976-4 , pp. 64 .
- ^ 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 .