TOPICS
Search

Crossed Prism Graph


CrossedPrismGraph

A n-crossed prism graph for positive even n (a term introduced here for the first time), is a graph obtained by taking two disjoint cycle graphs C_n and adding edges (v_k,v_(2k+1)) and (v_(k+1),v_(2k)) for k=1, 3, ..., (n-1).

The crossed prism graphs are cubic vertex-transitive (and hence appear in Read and Wilson 1998, though without any designation indicating membership in a special graph family), weakly regular, Hamiltonian, and Hamilton-laceable. The 2n-crossed prism graphs are toroidal for n>2 (E. Weisstein, May 9, 2023).

Simmons (2014) used the term "polygonal bigraph on 4m vertices" for graphs isomorphic to the m-crossed prism graph and investigated the Hamilton-laceability and structure of Hamiltonian paths in these graphs.

The first few crossed prism graphs and some of their properties are implemented in the Wolfram Language as GraphData[{"CrossedPrism", n}].

The n-crossed prism graph has independence polynomial

 I_n(x)=2^(-n)[(1+2x(2+x)-sqrt((1+2x)(1+6x)))^n+(1+2x(2+x)+sqrt((1+2x)(1+6x)))^n],

which has recurrence equation

 I_n(x)=(2x^2+4x+1)I_(n-1)(x)-x^2(x^2+4x+2)I_(n-2)(x).

The n-crossed prism graph is isomorphic to the Haar graph H(2^(n+1)+2^(n/2)+1) and to the (1,2n,n-1)-honeycomb toroidal graph. Other special cases are summarized in the following table.


See also

Crossed Graph, Cycle Graph, Cubic Vertex-Transitive Graph, Cubical Graph, Franklin Graph, Helm Graph, Honeycomb Toroidal Graph, Ladder Graph, Möbius Ladder, Prism Graph, Web Graph

Explore with Wolfram|Alpha

References

Read, R. C. and Wilson, R. J. "Cubic Polyhedral Graphs: 8-16 Vertices." In An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 159-163, 1998.Simmons, G. J. "A Surprising Regularity in the Number of Hamilton Paths in Polygonal Bigraphs." Ars Combin. 115, 335-341, 2014.

Referenced on Wolfram|Alpha

Crossed Prism Graph

Cite this as:

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

Subject classifications