Ladder graph

Ladder graph
Ladder graph
	The ladder graph L8.
Vertices
Edges
Chromatic number
Chromatic index
Properties	Unit distance; Hamiltonian; Planar; Bipartite
Notation
	Table of graphs and parameters

In the mathematical field of graph theory, the ladder graph $L n$ is a planar, undirected graph with $2 n$ vertices and $3 n - 2$ edges.[1]

The ladder graph can be obtained as the Cartesian product of two path graphs, one of which has only one edge: $L n,1 = P n \times P 2$ .[2][3]

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 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}-3x+3)^{(n-1)}$ .

The ladder graphs L₁, L₂, L₃, L₄ and L₅.

The chromatic number of the ladder graph is 2.

Ladder rung graph

Sometimes the term "ladder graph" is used for the n × P₂ ladder rung graph, which is the graph union of n copies of the path graph P₂.

The ladder rung graphs LR₁, LR₂, LR₃, LR₄, and LR₅.

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.[4] In symbols, CL_n = C_n × P₂. 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:

CL3	CL4	CL5	CL6	CL7	CL8

Möbius ladder

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

Two views of the Möbius ladder M₁₆ .

References

Weisstein, Eric W. "Ladder Graph". MathWorld.
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.
Chen, Yichao; Gross, Jonathan L.; Mansour, Toufik (September 2013). "Total Embedding Distributions of Circular Ladders". Journal of Graph Theory. 74 (1): 32–57. CiteSeerX 10.1.1.297.2183. doi:10.1002/jgt.21690. S2CID 6352288.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Weisstein, Eric W. "Ladder Graph". MathWorld.

[2] Hosoya, H. and Harary, F. "On the Matching Properties of Three Fence Graphs." J. Math. Chem. 12, 211-218, 1993.

[3] Noy, M. and Ribó, A. "Recursively Constructible Families of Graphs." Adv. Appl. Math. 32, 350-363, 2004.

[4] Chen, Yichao; Gross, Jonathan L.; Mansour, Toufik (September 2013). "Total Embedding Distributions of Circular Ladders". Journal of Graph Theory. 74 (1): 32–57. CiteSeerX 10.1.1.297.2183. doi:10.1002/jgt.21690. S2CID 6352288.