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''. ...

graph – 6 vertices, 9 edges *

Cubical graph In geometry, a cube is a three-dimensional space, three-dimensional solid object bounded by six square (geometry), square faces, Facet (geometry), facets or sides, with three meeting at each vertex (geometry), vertex. Viewed from a corner it i ...

– 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 a ...

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 t ...

graph – 12 vertices, 18 edges *

Heptagonal prism In geometry, the heptagonal prism is a prism with heptagonal base. This polyhedron has 9 faces, 21 edges, and 14 vertices.. Area The area of a right heptagonal prism with height h and with a side length of L and apothem a_p is given by: :A = 7 ...

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 polygon In geometry, a star polygon is a type of non- convex polygon. Regular star polygons have been studied in depth; while star polygons in general appear not to have been formally defined, certain notable ones can arise through truncation operation ...

s 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 o ...

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

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ ...

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 Ca ...

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. Present ...

\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 graph In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings. Equivalent definitions Cir ...

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 The term regular can mean normal or in accordance with rules. It may refer to: People * Moses Regular (born 1971), America football player Arts, entertainment, and media Music * "Regular" (Badfinger song) * Regular tunings of stringed instrum ...

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 bipa ...

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-c ...

s, they are also 3-vertex-connected

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

s. 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-factorization In graph theory, a factor of a graph ''G'' is a spanning subgraph, i.e., a subgraph that has the same vertex set as ''G''. A ''k''-factor of a graph is a spanning ''k''- regular subgraph, and a ''k''-factorization partitions the edges of the gr ...

s. 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, blue ...

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 tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...

s 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 cub ...

s. They form one of the few known infinite families of

cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system ...

partial cubes, and (except for four sporadic examples) the only vertex-transitive cubic partial cubes. The pentagonal prism is one of the

forbidden minors In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden ...

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 gr ...

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 graph In the mathematical field of graph theory, an antiprism graph is a graph that has one of the antiprisms as its skeleton. An -sided antiprism has vertices and edges. They are regular, polyhedral (and therefore by necessity also 3-vertex-connect ...

s (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 ...

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 graph In the mathematical field of graph theory, an Archimedean graph is a graph that forms the skeleton of one of the Archimedean solids. There are 13 Archimedean graphs, and all of them are regular, polyhedral (and therefore by necessity also 3-verte ...

s. 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 In the mathematical field of graph theory, the ladder graph is a planar, undirected graph with vertices and edges. The ladder graph can be obtained as the Cartesian product of two path graphs, one of which has only one edge: . Propertie ...

. 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 utilit ...

References

{{reflist Graph families Regular graphs Planar graphs