TOPICS
Search

Prism Graph


PrismGraph

A prism graph, denoted Y_n, D_n (Gallian 1987), or Pi_n (Hladnik et al. 2002), and sometimes also called a circular ladder graph and denoted CL_n (Gross and Yellen 1999, p. 14), is a graph corresponding to the skeleton of an n-prism. Prism graphs are therefore both planar and polyhedral. An n-prism graph has 2n nodes and 3n edges, and is equivalent to the generalized Petersen graph P_(n,1). For odd n, the n-prism is isomorphic to the circulant graph Ci_(2n)(2,n), as can be seen by rotating the inner cycle by 180 degrees and increasing its radius to equal that of the outer cycle in the top embeddings above. In addition, for odd n, Y_n is isomorphic to Ci_(2n)(4,n), Ci_(2n)(6,n), ..., Ci_(2n)(n-1,n).

Y_n is isomorphic to the graph Cartesian product P_2 square C_n, where P_2 is the path graph on two nodes and C_n is the cycle graph on n nodes. As a result, it is a unit-distance graph (Horvat and Pisanski 2010).

The prism graph Y_n is equivalent to the Cayley graph of the dihedral group D_(2n) with respect to the generating set {x,x^(-1),y} (Biggs 1993, p. 126).

The prism graph Y_3 is the line graph of the complete bipartite graph K_(2,3). The prism graph Y_4 is isomorphic with the cubical graph. The 2n-prism graph is isomorphic to the Haar graph H(2^2n-1+3).

Prism graphs are graceful (Gallian 1987, Frucht and Gallian 1988, Gallian 2018).

The numbers of directed Hamiltonian paths on the n-prism graph for n=3, 4, ... are 60, 144, 260, 456, 700, 1056, 1476, ... (OEIS A124350), which has the beautiful closed form

 |HP(n)|=4n(|_1/2n^2_|+1),

where |_x_| is the floor function (M. Alekseyev, pers. comm., Feb. 7, 2008).

PrismGraphCycles3

The numbers of graph cycles on the n-prism graph for n=3, 4, ... are 14, 28, 52, 94, 170, ... (OEIS A077265), illustrated above for n=3.

The graph Cartesian product Y_n square K_2 is ismorphic to the torus grid graph C_4 square K_2.

The bipartite double graph of prism graph Y_n for n odd is the prism graph Y_(2n).

Precomputed properties of prism graphs are available in the Wolfram Language as GraphData[{"Prism", n}].


See also

Antiprism Graph, Circulant Graph, Crossed Prism Graph, Cubical Graph, Cycle Graph, Generalized Petersen Graph, Helm Graph, Ladder Graph, Möbius Ladder, Prism, Stacked Prism Graph, Web Graph

Explore with Wolfram|Alpha

References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Gallian, J. "Labeling Prisms and Prism Related Graphs." Congr. Numer. 59, 89-100, 1987.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gross, J. T. and Yellen, J. Graph Theory and Its Applications. Boca Raton, FL: CRC Press, p. 14, 1999.Frucht R. and Gallian, J. A. "Labeling Prisms." Ars Combin. 26, 69-82, 1988.Hladnik, M.; Marušič, D.; and Pisanski, T. "Cyclic Haar Graphs." Disc. Math. 244, 137-153, 2002.Horvat, B. and Pisanski, T. "Products of Unit Distance Graphs." Disc. Math. 310, 1783-1792, 2010.Hosoya, H. and Harary, F. "On the Matching Properties of Three Fence Graphs." J. Math. Chem. 12, 211-218, 1993.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 263 and 270, 1998.Sloane, N. J. A. Sequences A077265 and A124350 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Prism Graph

Cite this as:

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

Subject classifications