# Ladder graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Ladder_graph
> Markdown URL: https://mediated.wiki/source/Ladder_graph.md
> Source: https://en.wikipedia.org/wiki/Ladder_graph
> Source revision: 1342990439
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{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 = <math>\begin{cases}
3 & \text{if } n > 2 \\  2 & \text{if } n = 2 \\  1 & \text {if } n = 1  \end{cases}</math>
 |notation = {{tmath|L_n}}
 | properties = [Unit distance](/source/Unit_distance_graph)<br>[Hamiltonian](/source/Hamiltonian_graph)<br>[Planar](/source/planar_graph)<br>[Bipartite](/source/Bipartite_graph)
}}

In the [mathematical](/source/mathematics) field of [graph theory](/source/graph_theory), the '''ladder graph''' {{mvar|L{{sub|n}}}} is a [planar](/source/planar_graph), [undirected graph](/source/undirected_graph) with {{math|2''n''}} [vertices](/source/Vertex_(graph_theory)) and {{math|3''n'' − 2}} edges.<ref>{{MathWorld|urlname=LadderGraph|title=Ladder Graph}}</ref>

The ladder graph can be obtained as the [Cartesian product](/source/Cartesian_product_of_graphs) of two [path graph](/source/path_graph)s, one of which has only one edge: {{math|1=''L''{{sub|''n''}} = ''P''{{sub|''n''}} □ ''P''{{sub|2}}}}.<ref>[Hosoya, H.](/source/Haruo_Hosoya) and [Harary, F.](/source/Frank_Harary) "On the Matching Properties of Three Fence Graphs." J. Math. Chem. 12, 211-218, 1993.</ref><ref>Noy, M. and Ribó, A. "Recursively Constructible Families of Graphs." Adv. Appl. Math. 32, 350-363, 2004.</ref>

==Properties==
By construction, the ladder graph L<sub>''n''</sub> is isomorphic to the [grid graph](/source/grid_graph) ''G''<sub>2,''n''</sub> and looks like a ladder with ''n'' rungs. It is [Hamiltonian](/source/Hamiltonian_graph) with girth 4 (if ''n>1'') and [chromatic index](/source/chromatic_index) 3 (if ''n>2'').

The [chromatic number](/source/chromatic_number) of the ladder graph is 2 and its [chromatic polynomial](/source/chromatic_polynomial) is <math>(x-1)x(x^2-3x+3)^{(n-1)}</math>.

thumb|450px|left|The ladder graphs ''L''<sub>1</sub>, ''L''<sub>2</sub>, ''L''<sub>3</sub>, ''L''<sub>4</sub> and ''L''<sub>5</sub>.

<gallery>
Image:Ladder graph L8 2COL.svg|The [chromatic number](/source/chromatic_number) of the ladder graph is&nbsp;2.
</gallery>

==Ladder rung graph==
Sometimes the term "ladder graph" is used for the ''nP''<sub>2</sub> '''ladder rung graph''', which is the graph union of ''n'' copies of the path graph ''P''<sub>2</sub>.
thumb|450px|left|The ladder rung graphs ''LR''<sub>1</sub>, ''LR''<sub>2</sub>, ''LR''<sub>3</sub>, ''LR''<sub>4</sub>, and ''LR''<sub>5</sub>.
{{Clear}}

== Circular ladder graph ==
{{main|Prism graph}}
The '''circular ladder graph''' ''CL''<sub>''n''</sub> is constructible by connecting the four 2-degree vertices in a ''straight'' way, or by the Cartesian product of a cycle of length ''n''&nbsp;&ge;&nbsp;3 and an edge.<ref>{{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](/source/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 }}</ref>
In symbols, {{nowrap|1=''CL''<sub>''n''</sub> = ''C''<sub>''n''</sub> □ ''P''<sub>2</sub>}}. It has 2''n'' nodes and 3''n'' edges.
Like the ladder graph, it is [connected](/source/connected_graph), [planar](/source/planar_graph) and [Hamiltonian](/source/Hamiltonian_cycle), but it is [bipartite](/source/bipartite_graph) if and only if ''n'' is even.

Circular ladder graph are the [polyhedral graph](/source/polyhedral_graph)s of prisms, so they are more commonly called '''prism graphs'''.

Circular ladder graphs:
{| class=wikitable
|- align=center
|100x87px<BR>CL<sub>3</sub>
|100x87px<BR>CL<sub>4</sub>
|100x87px<BR>CL<sub>5</sub>
|100x87px<BR>CL<sub>6</sub>
|100x87px<BR>CL<sub>7</sub>
|100x87px<BR>CL<sub>8</sub>
|}

== Möbius ladder ==
{{main|Möbius ladder}}
Connecting the four 2-degree vertices of a standard ladder graph ''crosswise'' creates a [cubic graph](/source/cubic_graph) called a Möbius ladder.
thumb|upright=1.35|left|Two views of the Möbius ladder ''M''<sub>16</sub> .
{{Clear}}

== References ==
{{reflist}}

Category:Parametric families of graphs
Category:Planar graphs

---
Adapted from the Wikipedia article [Ladder graph](https://en.wikipedia.org/wiki/Ladder_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Ladder_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.