• Source: Ladder graph

In the mathematical field of graph theory, the ladder graph Ln is a planar, undirected graph with 2n vertices and 3n – 2 edges.
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.




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



(
x
−
1
)
x
(

x

2


−
3
x
+
3

)

(
n
−
1
)




{\displaystyle (x-1)x(x^{2}-3x+3)^{(n-1)}}

.









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.
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:




Möbius ladder



Connecting the four 2-degree vertices crosswise creates a cubic graph called a Möbius ladder.




References

Kata Kunci Pencarian:

• Ladder graph
• Path graph
• Wagner graph
• Möbius ladder
• Schild's Ladder
• Cartesian product of graphs
• Loop (graph theory)
• Forbidden graph characterization
• Petersen graph
• Prism graph