TOPICS
Search

Ladder Rung Graph


LadderRungGraph

Ball and Coxeter (1987, pp. 277-278) define the ladder graph nP_2, here called the ladder rung graph, of order n as the graph union of n copies of the path graph P_2.

The n-ladder rung graph is isomorphic to the Haar graph H(2^(n-1)) and to the Knödel graph W_(1,2n). Kneser graphs of the form K(2n,n) are ladder rung graphs of order (2n; n), where (2n; n) is a central binomial coefficient.

The graph complement of nP_2 is the cocktail party graph K_(n×n).

If the restriction j,k<n in the I graph I(n,j,k) is loosened, nP_2 corresponds to I(n,n,n).

Ladder rung graphs are trivially unit-distance graphs.

nP_2 has chromatic polynomial, independence polynomial, and matching polynomial are given by

pi_n(x)=x^n(x-1)^n
(1)
I_n(x)=(2x+1)^n
(2)
mu(x)=(x-1)^n(x+1)^n,
(3)

with corresponding recurrence equations

pi_n(z)=z(z-1)pi_(n-1)(z)
(4)
I_n(x)=(2x+1)I_(n-1)(x)
(5)
mu_n(x)=(x-1)(x+1)mu_(n-1)(x).
(6)

The bipartite double graph of nP_2 is (2n)P_2.


See also

I Graph Kneser Graph, Knödel graph, Ladder Graph, Path Graph, Prism 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.

Referenced on Wolfram|Alpha

Ladder Rung Graph

Cite this as:

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

Subject classifications