In themathematical field ofgraph theory, aprism graph is agraph that has one of theprisms as its skeleton.

The individual graphs may be named after the associated solid:

• Triangular prism graph – 6 vertices, 9 edges
• Cubical graph – 8 vertices, 12 edges
• Pentagonal prism graph – 10 vertices, 15 edges
• Hexagonal prism graph – 12 vertices, 18 edges
• Heptagonal prism graph – 14 vertices, 21 edges
• Octagonal prism graph – 16 vertices, 24 edges
• ...

Y3 = GP(3,1)

Y4 =Q3 = GP(4,1)

Y5 = GP(5,1)

Y6 = GP(6,1)

Y7 = GP(7,1)

Y8 = GP(8,1)

Although geometrically thestar polygons also form the faces of a different sequence of (self-intersecting and non-convex) prismatic polyhedra, the graphs of these star prisms are isomorphic to the prism graphs, and do not form a separate sequence of graphs.

Prism graphs are examples ofgeneralized Petersen graphs, with parameters GP(n,1). They may also be constructed as theCartesian product of acycle graph with a single edge.^[1]

As with many vertex-transitive graphs, the prism graphs may also be constructed asCayley graphs. The order-ndihedral group is the group of symmetries of a regularn-gon in the plane; it acts on then-gon by rotations and reflections. It can be generated by two elements, a rotation by an angle of 2π/n and a single reflection, and its Cayley graph with this generating set is the prism graph. Abstractly, the group has thepresentation${\displaystyle ⟨r,f\mid r^n,f^2,(rf{)}^2⟩}$ (wherer is a rotation andf is a reflection or flip) and the Cayley graph hasr andf (orr,r⁻¹, andf) as its generators.^[1]

Then-gonal prism graphs with odd values ofn may be constructed ascirculant graphs${\displaystyle C_{2n}^{2,n}}$.However, this construction does not work for even values of n.^[1]

The graph of ann-gonal prism has 2n vertices and 3n edges. They areregular,cubic graphs.Since the prism has symmetries taking each vertex to each other vertex, the prism graphs arevertex-transitive graphs.Aspolyhedral graphs, they are also3-vertex-connectedplanar graphs. Every prism graph has aHamiltonian cycle.^[2] even sided prism graphs arebipartite graphs.

Among allbiconnectedcubic graphs, the prism graphs have within a constant factor of the largest possible number of1-factorizations. A 1-factorization is a partition of the edge set of the graph into three perfect matchings, or equivalently anedge coloring of the graph with three colors. Every biconnectedn-vertex cubic graph hasO(2^n/2) 1-factorizations, and the prism graphs haveΩ(2^n/2) 1-factorizations.^[3]

The number ofspanning trees of ann-gonal prism graph is given by the formula^[4]

${\displaystyle \frac{n}{2}((2+\sqrt{3}{)}^n+(2-\sqrt{3}{)}^n-2)}$

Forn = 3, 4, 5, ... these numbers are

75, 384, 1805, 8100, 35287, 150528, ... (sequenceA006235 in theOEIS).

Then-gonal prism graphs for even values ofn arepartial cubes. They form one of the few known infinite families ofcubic partial cubes, and (except for four sporadic examples) the only vertex-transitive cubic partial cubes.^[5]

The pentagonal prism is one of theforbidden minors for the graphs oftreewidth three.^[6] The triangular prism and cube graph have treewidth exactly three, but all larger prism graphs have treewidth four.

Other infinite sequences of polyhedral graph formed in a similar way from polyhedra with regular-polygon bases include theantiprism graphs (graphs ofantiprisms) andwheel graphs (graphs ofpyramids). Other vertex-transitive polyhedral graphs include theArchimedean graphs.

If the two cycles of a prism graph are broken by the removal of a single edge in the same position in both cycles, the result is aladder graph. If these two removed edges are replaced by two crossed edges, the result is a non-planar graph called aMöbius ladder.^[7]

Acrossed prism graph is similar but pairs up lateral crossed edges, alternating forward and backwards, for even-sided prisms. The set are alsoregular, vertex transitivecubic graphs, andbipartite graphs (also called bicubic graphs).^[8] A 4-crossed prism graph is the same as thecubical graph with 8 vertices, 12 edges. A 6-crossed prism graph is also theFranklin graph with 12 vertices, 18 edges. InAn Atlas of Graphs the first few are listed in the set ofConnected cubic transitive graphs indexed as Ct5, Ct12, Ct19, Ct29, Ct42, Ct54, and Ct74 for 4, 6, 8, 10, 12, 14, and 16 sides respectively.^[9]

First crossed prism graphs as 2 rings of vertices

4	6	8	10	12	14	16
cubical graph	Franklin graph	Ct19	Ct29	Ct42	Ct54	Ct74

• Graph families
• Regular graphs
• Planar graphs

• Articles with short description
• Short description matches Wikidata