Ladder graph

Ladder graph
File:Ladder graph L8.svg The ladder graph L8.
Vertices	⁠$2n$⁠
Edges	⁠$3n-2$⁠
Chromatic number	⁠$2$⁠
Chromatic index	$\{\begin{array}{cc}3& \text{if }n>2\\ 2& \text{if }n=2\\ 1& \text{if }n=1\end{array}$
Properties	Unit distance Hamiltonian Planar Bipartite
Notation	⁠$L_n$⁠
Table of graphs and parameters

In the mathematical field of graph theory, the ladder graph L_n is a planar, undirected graph with 2n vertices and 3n − 2 edges.

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₂.

Properties

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)}$.

File:Ladder graphs.svg

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

• The chromatic number of the ladder graph is 2.
  The chromatic number of the ladder graph is 2.

Ladder rung graph

Sometimes the term "ladder graph" is used for the n × P₂ ladder rung graph, which is the graph union of n copies of the path graph P₂.

File:Ladder rung graphs.svg

The ladder rung graphs LR₁, LR₂, LR₃, LR₄, and LR₅.

Circular ladder graph

Main article: Prism graph

The circular ladder graph CL_n 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. 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.

Circular ladder graph are the polyhedral graphs of prisms, so they are more commonly called prism graphs.

Circular ladder graphs:

File:Triangular prismatic graph.svg CL3

File:Cubical graph.svg CL4

File:Pentagonal prismatic graph.svg CL5

File:Hexagonal prismatic graph.svg CL6

File:Heptagonal prismatic graph.svg CL7

File:Octagonal prismatic graph.svg CL8

Möbius ladder

Main article: Möbius ladder

Connecting the four 2-degree vertices of a standard ladder graph crosswise creates a cubic graph called a Möbius ladder.

File:Moebius-ladder-16.svg

Two views of the Möbius ladder M₁₆ .