In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a prism graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

that has one of the

prism Prism usually refers to: * Prism (optics), a transparent optical component with flat surfaces that refract light * Prism (geometry), a kind of polyhedron Prism may also refer to: Science and mathematics * Prism (geology), a type of sedimentary ...

s as its skeleton.

Examples

The individual graphs may be named after the associated solid: *

Triangular prism In geometry, a triangular prism is a three-sided prism; it is a polyhedron made of a triangular base, a translated copy, and 3 faces joining corresponding sides. A right triangular prism has rectangular sides, otherwise it is ''oblique''. A ...

graph – 6 vertices, 9 edges *

Cubical graph In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross. The cube is the only r ...

– 8 vertices, 12 edges *

Pentagonal prism In geometry, the pentagonal prism is a prism with a pentagonal base. It is a type of heptahedron with seven faces, fifteen edges, and ten vertices. As a semiregular (or uniform) polyhedron If faces are all regular, the pentagonal prism is ...

graph – 10 vertices, 15 edges *

Hexagonal prism In geometry, the hexagonal prism is a prism with hexagonal base. Prisms are polyhedrons; this polyhedron has 8 faces, 18 edges, and 12 vertices.. Since it has 8 faces, it is an octahedron. However, the term ''octahedron'' is primarily used ...

graph – 12 vertices, 18 edges * Heptagonal prism graph – 14 vertices, 21 edges *

Octagonal prism In geometry, the octagonal prism is the sixth in an infinite set of prisms, formed by rectangular sides and two regular octagon caps. If faces are all regular, it is a semiregular polyhedron. Symmetry Images The octagonal prism can also ...

graph – 16 vertices, 24 edges * ... 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.

Construction

Prism graphs are examples of

generalized Petersen graph In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways ...

s, with parameters GP(''n'',1). They may also be constructed as the Cartesian product of a

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

with a single edge. As with many vertex-transitive graphs, the prism graphs may also be constructed as

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...

s. The order-''n''

dihedral group In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ...

is the group of symmetries of a regular ''n''-gon in the plane; it acts on the ''n''-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 the

presentation A presentation conveys information from a speaker to an audience. Presentations are typically demonstrations, introduction, lecture, or speech meant to inform, persuade, inspire, motivate, build goodwill, or present a new idea/product. Presenta ...

\langle r,f\mid r^n, f^2, (rf)^2\rangle

(where ''r'' is a rotation and ''f'' is a reflection or flip) and the Cayley graph has ''r'' and ''f'' (or ''r'', ''r''⁻¹, and ''f'') as its generators. The ''n''-gonal prism graphs with odd values of ''n'' may be constructed as circulant graphs

C_^

. However, this construction does not work for even values of ''n''.

Properties

The graph of an ''n''-gonal prism has 2''n'' vertices and 3''n'' edges. They are regular,

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bi ...

s. Since the prism has symmetries taking each vertex to each other vertex, the prism graphs are

vertex-transitive graph In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive ...

s. As

polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-con ...

s, they are also 3-vertex-connected planar graphs. Every prism graph has a

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

. Among all biconnected

s, 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 In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blu ...

of the graph with three colors. Every biconnected ''n''-vertex cubic graph has ''O''(2^''n''/2) 1-factorizations, and the prism graphs have ''Ω''(2^''n''/2) 1-factorizations. The number of spanning trees of an ''n''-gonal prism graph is given by the formula :

\frac\bigl( (2+\sqrt)^n+(2-\sqrt)^n-2)\bigr.

For ''n'' = 3, 4, 5, ... these numbers are :75, 384, 1805, 8100, 35287, 150528, ... . The ''n''-gonal prism graphs for even values of ''n'' are

partial cube In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial c ...

s. 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. The pentagonal prism is one of the forbidden minors for the graphs of

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

three. The triangular prism and cube graph have treewidth exactly three, but all larger prism graphs have treewidth four.

Related graphs

Other infinite sequences of polyhedral graph formed in a similar way from polyhedra with regular-polygon bases include the antiprism graphs (graphs of

antiprism In geometry, an antiprism or is a polyhedron composed of two parallel direct copies (not mirror images) of an polygon, connected by an alternating band of triangles. They are represented by the Conway notation . Antiprisms are a subclass o ...

s) and

wheel graph A wheel is a circular component that is intended to rotate on an axle bearing. The wheel is one of the key components of the wheel and axle which is one of the six simple machines. Wheels, in conjunction with axles, allow heavy objects to be ...

s (graphs of

pyramids A pyramid (from el, πυραμίς ') is a structure whose outer surfaces are triangular and converge to a single step at the top, making the shape roughly a pyramid in the geometric sense. The base of a pyramid can be trilateral, quadrilat ...

). 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 In graph theory, the Möbius ladder , for even numbers , is formed from an by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a cubic, circulant graph, so-named because (with the exception of (the utili ...

References

{{reflist Graph families Regular graphs Planar graphs