{{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<br>Hamiltonian<br>Planar<br>Bipartite }}
In the mathematical field of graph theory, the '''ladder graph''' {{mvar|L{{sub|n}}}} is a planar, undirected graph with {{math|2''n''}} vertices and {{math|3''n'' − 2}} edges.<ref>{{MathWorld|urlname=LadderGraph|title=Ladder Graph}}</ref>
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''}} = ''P''{{sub|''n''}} □ ''P''{{sub|2}}}}.<ref>Hosoya, H. and Harary, F. "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 ''G''<sub>2,''n''</sub> 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>(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 of the ladder graph is 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'' ≥ 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|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, 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 |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 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