Ladder graph
{{Short description|Planar, undirected graph with 2n vertices and 3n-2 edges}}
{{infobox graph
| name = Ladder graph
| image = 120px
| image_caption = The ladder graph {{math|L{{sub|8}}}}.
| vertices = {{tmath|2n}}
| edges = {{tmath|3n-2}}
| automorphisms =
| chromatic_number = {{tmath|2}}
| chromatic_index =
3 & \text{if } n > 2 \\ 2 & \text{if } n = 2 \\ 1 & \text {if } n = 1 \end{cases}
|notation = {{tmath|L_n}}
| properties = Unit distance
Hamiltonian
Planar
Bipartite
}}
In the mathematical field of graph theory, the ladder graph {{mvar|L{{sub|n}}}} is a planar, undirected graph with {{math|2n}} vertices and {{math|3n − 2}} edges.{{MathWorld|urlname=LadderGraph|title=Ladder Graph}}
The ladder graph can be obtained as the Cartesian product of two path graphs, one of which has only one edge: {{math|1=L{{sub|n,1}} = P{{sub|n}} × P{{sub|2}}}}.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.
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 .
Image:Ladder graph L8 2COL.svg|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.
{{Clear}}
Circular ladder graph
{{main|Prism 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.{{cite journal|last1=Chen|first1=Yichao|last2=Gross|first2=Jonathan L.|last3=Mansour|first3=Toufik|authorlink3=Toufik Mansour|title=Total Embedding Distributions of Circular Ladders|journal=Journal of Graph Theory|date=September 2013|volume=74|issue=1|pages=32–57|doi=10.1002/jgt.21690|citeseerx=10.1.1.297.2183|s2cid=6352288 }}
In symbols, {{nowrap|1=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:
| class=wikitable |
| align=center
|100px |100px |100px |100px |100px |100px |
Möbius ladder
{{main|Möbius ladder}}
Connecting the four 2-degree vertices crosswise creates a cubic graph called a Möbius ladder.
{{Clear}}