In the
mathematical field of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the ladder graph is a
planar,
undirected graph with
vertices and edges.
The ladder graph can be obtained as the
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
of two
path graphs, one of which has only one edge: .
Properties
By construction, the ladder graph L
''n'' is isomorphic to the
grid graph ''G''
2,''n'' and looks like a ladder with ''n'' rungs. It is
Hamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified 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'' × ''P''
2 ladder rung graph, which is the graph union of ''n'' copies of the path graph P
2.
Circular ladder graph
The circular ladder graph ''CL''
''n'' 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.
In symbols, . It has 2''n'' nodes and 3''n'' edges.
Like the ladder graph, it is
connected,
planar and
Hamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
, but it is
bipartite
Bipartite may refer to:
* 2 (number)
* Bipartite (theology), a philosophical term describing the human duality of body and soul
* Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...
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:
Möbius ladder
Connecting the four 2-degree vertices ''crosswise'' creates a
cubic graph called a Möbius ladder.
References
{{reflist
Parametric families of graphs
Planar graphs