[go: up one dir, main page]
TOPICS
Search

Ladder Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
LadderGraph

The n-ladder graph can be defined as L_n=P_2 square P_n, where P_n is a path graph (Hosoya and Harary 1993; Noy and Ribó 2004, Fig. 1). It is therefore equivalent to the 2×n grid graph. The ladder graph is named for its resemblance to a ladder consisting of two rails and n rungs between them (though starting immediately at the bottom and finishing at the top with no offset).

Hosoya and Harary (1993) also use the term "ladder graph" for the graph Cartesian product K_2 square C_n, where K_2 is the complete graph on two nodes and C_n is the cycle graph on n nodes. This class of graph is however more commonly known as a prism graph.

Ball and Coxeter (1987, pp. 277-278) use the term "ladder graph" to refer to the graph known in this work as the ladder rung graph.

The ladder graph P_2 square P_n is graceful (Maheo 1980).

The chromatic polynomial (cf. Yadav et al. 2024), independence polynomial, and reliability polynomial of the ladder graph L_n are given by

pi_n(z)=(z-1)z(z^2-3z+3)^(n-1)
(1)
I_n(z)=2^(-(n+1))[(s-3x-1)(x-s+1)^n+(s+3x+1)(x+s+1)^n]
(2)
C(p)=((p-1)^(2n-1))/(2^nsqrt(p(9p+2)+1))[(3p-sqrt(p(9p+2)+1)+1)^n-(3p+sqrt(p(9p+2)+1)+1)^n],
(3)

where s=sqrt(x^2+6x+1). Recurrence equations for the chromatic polynomial, independence polynomial, matching polynomial, rank polynomial, and reliability polynomial are given by

pi_n(z)=(z^2-3z+3)pi_(n-1)(z)
(4)
I_n(x)=(x+1)I_(n-1)(x)+xI_(n-2)(x)
(5)
mu_n(x)=(-2+x^2)mu_(n-1)(x)-x^2mu_(n-2)(x)+mu_(n-3)(x)
(6)
R_n(x,y)=(1+3x+4x^2+x^2y)R_(n-1)(x,y)-x^2(x+1)^2(y+1)R_(n-2)(x,y)
(7)
C_n(x)=(3x+1)C_(n-1)(x)-xC_(n-2)(x).
(8)

See also

Cocktail Party Graph, Crossed Prism Graph, Cycle Graph, Cyclotomic Graph, Gear Graph, Grid Graph, Hadamard Graph, Helm Graph, Ladder Rung Graph, Möbius Ladder, Path Graph, Prism Graph, Web Graph, Wheel Graph

Explore with Wolfram|Alpha

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987.Hosoya, H. and Harary, F. "On the Matching Properties of Three Fence Graphs." J. Math. Chem. 12, 211-218, 1993.Maheo, M. "Strongly Graceful Graphs." Disc. Math. 29, 39-46, 1980.Noy, M. and Ribó, A. "Recursively Constructible Families of Graphs." Adv. Appl. Math. 32, 350-363, 2004.Yadav, R.; Sehgal, A.; Sehgal, S.; and Malik, A. "The Chromatic Polynomial of Grid Graph P_3 square P_n." J. Appl. Math. Comput., 2024.

Referenced on Wolfram|Alpha

Ladder Graph

Cite this as:

Weisstein, Eric W. "Ladder Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LadderGraph.html

Subject classifications