# Prism graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Prism_graph
> Markdown URL: https://mediated.wiki/source/Prism_graph.md
> Source: https://en.wikipedia.org/wiki/Prism_graph
> Source revision: 1352721248
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Graph with a prism as its skeleton}}
In the [mathematical](/source/mathematics) field of [graph theory](/source/graph_theory), a '''prism graph''' is a [graph](/source/Graph_(discrete_mathematics)) that has one of the [prism](/source/prism_(geometry))s as its skeleton.

==Examples==
The individual graphs may be named after the associated solid:

* [Triangular prism](/source/Triangular_prism) graph – 6 vertices, 9 edges
* [Cubical graph](/source/Cubical_graph) – 8 vertices, 12 edges
* [Pentagonal prism](/source/Pentagonal_prism) graph – 10 vertices, 15 edges
* [Hexagonal prism](/source/Hexagonal_prism) graph – 12 vertices, 18 edges
* [Heptagonal prism](/source/Heptagonal_prism) graph – 14 vertices, 21 edges
* [Octagonal prism](/source/Octagonal_prism) graph – 16 vertices, 24 edges
* ...

{| class=wikitable
|- align=center
|100px<BR>Y<sub>3</sub> = GP(3,1)
|100px<BR>Y<sub>4</sub> = [Q<sub>3</sub>](/source/cubical_graph) = GP(4,1)
|100px<BR>Y<sub>5</sub> = GP(5,1)
|100px<BR>Y<sub>6</sub> = GP(6,1)
|100px<BR>Y<sub>7</sub> = GP(7,1)
|100px<BR>Y<sub>8</sub> = GP(8,1)
|}

Although geometrically the [star polygon](/source/star_polygon)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](/source/generalized_Petersen_graph)s, with parameters GP(''n'',1). 
They may also be constructed as the [Cartesian product](/source/Cartesian_product_of_graphs) of a [cycle graph](/source/cycle_graph) with a single edge.<ref name="mathworld"/>

As with many vertex-transitive graphs, the prism graphs may also be constructed as [Cayley graph](/source/Cayley_graph)s. The order-''n'' [dihedral group](/source/dihedral_group) 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{{pi}}/''n'' and a single reflection, and its Cayley graph with this generating set is the prism graph. Abstractly, the group has the [presentation](/source/presentation_of_a_group) <math>\langle r,f\mid r^n, f^2, (rf)^2\rangle</math> (where ''r'' is a rotation and ''f'' is a reflection or flip) and the Cayley graph has ''r'' and ''f'' (or ''r'', ''r''<sup>&minus;1</sup>, and ''f'') as its generators.<ref name="mathworld">{{mathworld | urlname = PrismGraph | title = Prism graph }}</ref>

The ''n''-gonal prism graphs with odd values of ''n'' may be constructed as [circulant graph](/source/circulant_graph)s <math>C_{2n}^{2,n}</math>.
However, this construction does not work for even values of&nbsp;''n''.<ref name="mathworld"/>

==Properties==
The graph of an ''n''-gonal prism has 2''n'' vertices and 3''n'' edges. They are [regular](/source/regular_graph), [cubic graph](/source/cubic_graph)s.
Since the prism has symmetries taking each vertex to each other vertex, the prism graphs are [vertex-transitive graph](/source/vertex-transitive_graph)s.
As [polyhedral graph](/source/polyhedral_graph)s, they are also [3-vertex-connected](/source/K-vertex-connected_graph) [planar graph](/source/planar_graph)s. Every prism graph has a [Hamiltonian cycle](/source/Hamiltonian_cycle).<ref>Read, R. C. and [Wilson, R. J.](/source/Robin_Wilson_(mathematician)) ''An Atlas of Graphs'', Oxford, England: Oxford University Press, 2004 reprint, Chapter 6 ''special graphs'' pp. 261, 270.</ref> even sided prism graphs are [bipartite graph](/source/bipartite_graph)s.

Among all [biconnected](/source/biconnected_graph) [cubic graph](/source/cubic_graph)s, the prism graphs have within a constant factor of the largest possible number of [1-factorization](/source/graph_factorization)s. A 1-factorization is a partition of the edge set of the graph into three perfect matchings, or equivalently an [edge coloring](/source/edge_coloring) of the graph with three colors. Every biconnected ''n''-vertex cubic graph has ''O''(2<sup>''n''/2</sup>) 1-factorizations, and the prism graphs have ''&Omega;''(2<sup>''n''/2</sup>) 1-factorizations.<ref>{{citation
 | last = Eppstein | first = David | authorlink = David Eppstein
 | doi = 10.7155/jgaa.00283
 | issue = 1
 | journal = [Journal of Graph Algorithms and Applications](/source/Journal_of_Graph_Algorithms_and_Applications)
 | mr = 3019198
 | pages = 35–55
 | title = The complexity of bendless three-dimensional orthogonal graph drawing
 | volume = 17
 | year = 2013| doi-access = free | arxiv = 0709.4087
 | s2cid = 2716392 }}. Eppstein credits the observation that prism graphs have close to the maximum number of 1-factorizations to a personal communication by [Greg Kuperberg](/source/Greg_Kuperberg).</ref>

The number of [spanning tree](/source/spanning_tree)s of an ''n''-gonal prism graph is given by the formula<ref>{{citation
 | last = Jagers | first = A. A.
 | doi = 10.1080/00207168808803639
 | issue = 2
 | journal = International Journal of Computer Mathematics
 | pages = 151–154
 | title = A note on the number of spanning trees in a prism graph
 | volume = 24
 | year = 1988}}.</ref>
:<math>\frac{n}{2}\bigl( (2+\sqrt{3})^n+(2-\sqrt{3})^n-2)\bigr.</math>
For ''n'' = 3, 4, 5, ... these numbers are
:75, 384, 1805, 8100, 35287, 150528, ... {{OEIS|A006235}}.

The ''n''-gonal prism graphs for even values of ''n'' are [partial cube](/source/partial_cube)s. They form one of the few known infinite families of [cubic](/source/cubic_graph) partial cubes, and (except for four sporadic examples) the only vertex-transitive cubic partial cubes.<ref>{{citation|title=Classification of vertex-transitive cubic partial cubes|first=Tilen|last=Marc|year=2015|arxiv=1509.04565|bibcode=2015arXiv150904565M}}.</ref>

The pentagonal prism is one of the [forbidden minors](/source/forbidden_graph_characterization) for the graphs of [treewidth](/source/treewidth) three.<ref>{{citation
 | last1 = Arnborg | first1 = Stefan
 | last2 = Proskurowski | first2 = Andrzej
 | last3 = Corneil | first3 = Derek G. | author3-link = Derek Corneil
 | doi = 10.1016/0012-365X(90)90292-P
 | issue = 1
 | journal = Discrete Mathematics
 | mr = 1045920
 | pages = 1–19
 | title = Forbidden minors characterization of partial 3-trees
 | volume = 80
 | year = 1990| doi-access = 
 }}.</ref> 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](/source/antiprism_graph)s (graphs of [antiprism](/source/antiprism)s) and [wheel graph](/source/wheel_graph)s (graphs of [pyramids](/source/Pyramid_(geometry))).  Other vertex-transitive polyhedral graphs include the [Archimedean graph](/source/Archimedean_graph)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](/source/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](/source/M%C3%B6bius_ladder).<ref>{{citation
  | last1 = Guy | first1 = Richard K. | author1-link = Richard K. Guy
  | last2 = Harary | first2 = Frank | author2-link = Frank Harary
  | title = On the Möbius ladders
  | journal = [Canadian Mathematical Bulletin](/source/Canadian_Mathematical_Bulletin)
  | volume = 10
  | year = 1967
  | issue = 4 | pages = 493–496
 | doi = 10.4153/CMB-1967-046-4 | doi-access=free
 | mr = 0224499}}.</ref>

A '''crossed prism graph''' is similar but pairs up lateral crossed edges, alternating forward and backwards, for even-sided prisms. The set are also [regular](/source/regular_graph), vertex transitive [cubic graph](/source/cubic_graph)s, and [bipartite graph](/source/bipartite_graph)s (also called bicubic graphs).<ref>{{mathworld | urlname = CrossedPrismGraph | title = Crossed prism graph }}</ref> A 4-crossed prism graph is the same as the [cubical graph](/source/cubical_graph) with 8 vertices, 12 edges. A 6-crossed prism graph is also the [Franklin graph](/source/Franklin_graph) with 12 vertices, 18 edges. In ''An Atlas of Graphs'' the first few are listed in the set of ''Connected cubic transitive graphs'' indexed as Ct5, Ct12, Ct19, Ct29, Ct42, Ct54, and Ct74 for 4, 6, 8, 10, 12, 14, and 16 sides respectively.<ref>Read, R. C. and Wilson, R. J. ''An Atlas of Graphs'', Oxford, England: Oxford University Press, 2004 reprint, Chapter 3 ''Regular graphs'' Connected cubic transitive graphs 4-18 vertices. pp. 161-163.</ref>

{| class=wikitable
|+ First crossed prism graphs as 2 rings of vertices
!4||6||8||10||12||14||16
|- align=center
||100px<BR>[cubical graph](/source/cubical_graph)
||100px<BR>[Franklin graph](/source/Franklin_graph)
||100px<BR>Ct19
||100px<BR>Ct29
||100px<BR>Ct42
||100px<BR>Ct54
||100px<BR>Ct74
|}

== References==
{{reflist}}

Category:Graph families
Category:Regular graphs
Category:Planar graphs

---
Adapted from the Wikipedia article [Prism graph](https://en.wikipedia.org/wiki/Prism_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Prism_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.