Top Qs
Timeline
Chat
Perspective

Ladder graph

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

Ladder graph
Remove ads

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 ...
Remove ads

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]

Remove ads

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.
Remove ads

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 content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads