Ladder graph

Ladder graph
The ladder graph L8.
Vertices	2n
Edges	n+2(n-1)
Chromatic number	2
Chromatic index	3 for n>2 2 for n=2 1 for n=1
Properties	Unit distance Hamiltonian Planar Bipartite
Notation	Ln

In the mathematical field of graph theory, the ladder graph L_n is a planar undirected graph with 2n vertices and n+2(n-1) edges.^[1]

The ladder graph can be obtained as the Cartesian product of two path graphs, one of which has only one edge: L_n,1 = P_n × P₁.^[2][3] Adding two more crossed edges connecting the four degree-two vertices of a ladder graph produces a cubic graph, the Möbius ladder.

By construction, the ladder graph L_n is isomorphic to the grid graph G_2,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 $(x-1)x(x^2-3x+3)^{(n-1)}$.

Circular ladder graph

The circular ladder graph CL_n is a the Cartesian product of a cycle of length n≥3 and an edge.^[4] In symbols, CL_n = C_n × P₁. 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.

Gallery

The ladder graphs L₁, L₂, L₃, L₄ and L₅.

• 

  The chromatic number of the ladder graph is 2.

References

1. Weisstein, Eric W., "Ladder Graph", MathWorld.
2. Hosoya, H. and Harary, F. "On the Matching Properties of Three Fence Graphs." J. Math. Chem. 12, 211-218, 1993.
3. Noy, M. and Ribó, A. "Recursively Constructible Families of Graphs." Adv. Appl. Math. 32, 350-363, 2004.
4. Chen, Yichao; Gross, Jonathan L.; Mansour, Toufik (September 2013). "Total Embedding Distributions of Circular Ladders". Journal of Graph Theory 74 (1): 32–57. doi:10.1002/jgt.21690.