Ladder graph

Planar, undirected graph with 2n vertices and 3n-2 edges From Wikipedia, the free encyclopedia

Ladder graph

In the mathematical field of graph theory, the ladder graph Ln is a planar, undirected graph with 2n vertices and 3n – 2 edges.[1]

Quick Facts Vertices, Edges ...
Ladder graph
Thumb
The ladder graph L8.
Vertices
Edges
Chromatic number
Chromatic index
PropertiesUnit distance
Hamiltonian
Planar
Bipartite
Notation
Table of graphs and parameters
Close

The ladder graph can be obtained as the Cartesian product of two path graphs, one of which has only one edge: Ln,1 = 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 .

Thumb
The ladder graphs L1, L2, L3, L4 and L5.

Ladder rung graph

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

Thumb
The ladder rung graphs LR1, LR2, LR3, LR4, and LR5.

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:

Thumb
CL3
Thumb
CL4
Thumb
CL5
Thumb
CL6
Thumb
CL7
Thumb
CL8

Möbius ladder

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

Thumb
Two views of the Möbius ladder M16 .

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.