A prism graph, denoted ,
(Gallian 1987), or
(Hladnik et al. 2002), and sometimes also called
a circular ladder graph and denoted
(Gross and Yellen 1999, p. 14), is a graph
corresponding to the skeleton of an
-prism. Prism graphs are therefore
both planar and polyhedral.
An
-prism graph has
nodes and
edges, and is equivalent to the generalized
Petersen graph
.
For odd
,
the
-prism is isomorphic to the circulant
graph
,
as can be seen by rotating the inner cycle by
and increasing its radius to equal that of the outer
cycle in the top embeddings above. In addition, for odd
,
is isomorphic to
,
, ...,
.
is isomorphic to the graph
Cartesian product
,
where
is the path graph on two nodes and
is the cycle graph on
nodes. As a result, it is a unit-distance
graph (Horvat and Pisanski 2010).
The prism graph
is equivalent to the Cayley graph of the dihedral
group
with respect to the generating set
(Biggs 1993, p. 126).
The prism graph
is the line graph of the complete
bipartite graph
.
The prism graph
is isomorphic with the cubical graph. The
-prism graph is isomorphic to the Haar
graph
.
Prism graphs are graceful (Gallian 1987, Frucht and Gallian 1988, Gallian 2018).
The numbers of directed Hamiltonian paths on the -prism graph for
, 4, ... are 60, 144, 260, 456, 700, 1056, 1476, ... (OEIS
A124350), which has the beautiful closed form
where
is the floor function (M. Alekseyev, pers.
comm., Feb. 7, 2008).
The numbers of graph cycles on the -prism graph for
, 4, ... are 14, 28, 52, 94, 170, ... (OEIS A077265),
illustrated above for
.
The graph Cartesian product is ismorphic to the torus
grid graph
.
The bipartite double graph of prism graph for
odd is the prism graph
.
Precomputed properties of prism graphs are available in the Wolfram Language as GraphData["Prism", n
].