Ladder graph
| Ladder graph | |
|---|---|
 The ladder graph L8. | |
| Vertices | [math]\displaystyle{ 2n }[/math] |
| Edges | [math]\displaystyle{ 3n-2 }[/math] |
| Chromatic number | [math]\displaystyle{ 2 }[/math] |
| Chromatic index | [math]\displaystyle{ \begin{cases} 3 & \text{if } n \gt 2 \\ 2 & \text{if } n = 2 \\ 1 & \text {if } n = 1 \end{cases} }[/math] |
| Properties | Unit distance Hamiltonian Planar Bipartite |
| Notation | [math]\displaystyle{ L_n }[/math] |
| Table of graphs and parameters | |
In the mathematical field of graph theory, the ladder graph Ln is a planar, undirected graph with 2n vertices and 3n – 2 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 × 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 [math]\displaystyle{ (x-1)x(x^2-3x+3)^{(n-1)} }[/math].
The chromatic number of the ladder graph is 2.
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.
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:
 CL3 |
 CL4 |
 CL5 |
 CL6 |
 CL7 |
 CL8 |
Möbius ladder
Connecting the four 2-degree vertices crosswise creates a cubic graph called a Möbius ladder.
References
- ↑ Weisstein, Eric W.. "Ladder Graph". http://mathworld.wolfram.com/LadderGraph.html.
- ↑ 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.
 |  |
