In the mathematical field of graph theory, a prism graph is a graph that has one of the prisms as its skeleton.
The individual graphs may be named after the associated solid:
Although geometrically the star 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 of generalized Petersen graphs, with parameters GP(n,1). They may also be constructed as the Cartesian product of a cycle graph with a single edge.
\langler,f\midrn,f2,(rf)2\rangle
The n-gonal prism graphs with odd values of n may be constructed as circulant graphs
| 2,n | |
| C | |
| 2n |
The graph of an n-gonal prism has 2n vertices and 3n edges. They are regular, cubic graphs.Since the prism has symmetries taking each vertex to each other vertex, the prism graphs are vertex-transitive graphs.As polyhedral graphs, they are also 3-vertex-connected planar graphs. Every prism graph has a Hamiltonian cycle.[1]
Among all biconnected cubic graphs, the prism graphs have within a constant factor of the largest possible number of 1-factorizations. A 1-factorization is a partition of the edge set of the graph into three perfect matchings, or equivalently an edge coloring of the graph with three colors. Every biconnected n-vertex cubic graph has O(2n/2) 1-factorizations, and the prism graphs have Ω(2n/2) 1-factorizations.[2]
The number of spanning trees of an n-gonal prism graph is given by the formula[3]
| n | |
| 2 |
l((2+\sqrt{3})n+(2-\sqrt{3})n-2)r.
75, 384, 1805, 8100, 35287, 150528, ... .
The n-gonal prism graphs for even values of n are partial cubes. They form one of the few known infinite families of cubic partial cubes, and (except for four sporadic examples) the only vertex-transitive cubic partial cubes.[4]
The pentagonal prism is one of the forbidden minors for the graphs of treewidth three.[5] 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 the antiprism graphs (graphs of antiprisms) and wheel graphs (graphs of pyramids). Other vertex-transitive polyhedral graphs include the Archimedean 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 a ladder graph. If these two removed edges are replaced by two crossed edges, the result is a non-planar graph called a Möbius ladder.[6]