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 Ln 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: Ln,1 = Pn × P1.[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 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 .
Circular ladder graph
The circular ladder graph CLn is a the Cartesian product of a cycle of length n≥3 and an edge.[4] In symbols, CLn = Cn × P1. 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 chromatic number of the ladder graph is 2.
References
- ↑ Weisstein, Eric W. "Ladder Graph". MathWorld.
- ↑ Hosoya, H. and Harary, F. "On the Matching Properties of Three Fence Graphs." J. Math. Chem. 12, 211-218, 1993.
- ↑ Noy, M. and Ribó, A. "Recursively Constructible Families of Graphs." Adv. Appl. Math. 32, 350-363, 2004.
- ↑ 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.