Ladder graph
Planar, undirected graph with 2n vertices and 3n-2 edges
From Wikipedia, the free encyclopedia
In the mathematical field of graph theory, the ladder graph Ln is a planar, undirected graph with 2n vertices and 3n − 2 edges.[1]
| Ladder graph | |
|---|---|
 The ladder graph L8. | |
| Vertices | |
| Edges | |
| Chromatic number | |
| Chromatic index | |
| Properties | Unit distance Hamiltonian Planar Bipartite |
| Notation | |
| Table of graphs and parameters | |
The ladder graph can be obtained as the Cartesian product of two path graphs, one of which has only one edge: Ln = Pn □ P2.[2][3]
Properties
By construction, the ladder graph Ln is isomorphic to the grid graph G2,n and looks like a ladder with n rungs. It is Hamiltonian with girth 4 (if n>1) and chromatic index 3 (if n>2).
The chromatic number of the ladder graph is 2 and its chromatic polynomial is .
The chromatic number of the ladder graph is 2.
Ladder rung graph
Sometimes the term "ladder graph" is used for the nP2 ladder rung graph, which is the graph union of n copies of the path graph P2.
Circular ladder graph
The circular ladder graph CLn is constructible by connecting the four 2-degree vertices in a straight way, or by the Cartesian product of a cycle of length n ≥ 3 and an edge.[4] In symbols, CLn = Cn □ P2. It has 2n nodes and 3n edges. Like the ladder graph, it is connected, planar and Hamiltonian, but it is bipartite if and only if n is even.
Circular ladder graph are the polyhedral graphs of prisms, so they are more commonly called prism graphs.
Circular ladder graphs:
 CL3 |
 CL4 |
 CL5 |
 CL6 |
 CL7 |
 CL8 |
Möbius ladder
Connecting the four 2-degree vertices of a standard ladder graph crosswise creates a cubic graph called a Möbius ladder.
