Prism graph

Last updated November 08, 2023

In the mathematical field of graph theory, a prism graph is a graph that has one of the prisms as its skeleton.

Examples

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

Y₃ = GP(3,1)	Y₄ = Q₃ = GP(4,1)	Y₅ = GP(5,1)	Y₆ = GP(6,1)	Y₇ = GP(7,1)	Y₈ = GP(8,1)

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 graphs, with parameters GP(n,1). They may also be constructed as the Cartesian product of a cycle graph with a single edge.^[1]

As with many vertex-transitive graphs, the prism graphs may also be constructed as Cayley graphs. The order-n 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 $π$ /n and a single reflection, and its Cayley graph with this generating set is the prism graph. Abstractly, the group has the presentation $\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.^[1]

The n-gonal prism graphs with odd values of n may be constructed as circulant graphs $C_{2n}^{2,n}$ . However, this construction does not work for even values of n.^[1]

Properties

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.^[2]

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(2^n/2) 1-factorizations, and the prism graphs have Ω(2^n/2) 1-factorizations.^[3]

The number of spanning trees of an n-gonal prism graph is given by the formula^[4]

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

For n = 3, 4, 5, ... these numbers are

75, 384, 1805, 8100, 35287, 150528, ... (sequence A006235 in the OEIS ).

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.^[5]

The pentagonal prism is one of the forbidden minors for the graphs of treewidth three.^[6] 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 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.^[7]

Related Research Articles

In geometry, an $n$ -gonal antiprism or $n$ -antiprism is a polyhedron composed of two parallel direct copies of an $n$ -sided polygon, connected by an alternating band of $2 n$ triangles. They are represented by the Conway notation $A n$ .

In geometry, a 4-polytope is a four-dimensional polytope. It is a connected and closed figure, composed of lower-dimensional polytopal elements: vertices, edges, faces (polygons), and cells (polyhedra). Each face is shared by exactly two cells. The 4-polytopes were discovered by the Swiss mathematician Ludwig Schläfli before 1853.

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.

In geometry, a prism is a polyhedron comprising an $n$ -sided polygon base, a second base which is a translated copy of the first, and $n$ other faces, necessarily all parallelograms, joining corresponding sides of the two bases. All cross-sections parallel to the bases are translations of the bases. Prisms are named after their bases, e.g. a prism with a pentagonal base is called a pentagonal prism. Prisms are a subclass of prismatoids.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical field of graph theory, a vertex-transitive graph is a graph $G$ in which, given any two vertices $v 1$ and $v 2$ of $G$ , there is some automorphism

In the mathematical field of graph theory, an edge-transitive graph is a graph $G$ such that, given any two edges $e 1$ and $e 2$ of $G$ , there is an automorphism of $G$ that maps $e 1$ to $e 2$ .

In the mathematical field of graph theory, a graph $G$ is symmetric if, given any two pairs of adjacent vertices $u 1 — v 1$ and $u 2 — v 2$ of $G$ , there is an automorphism

The cubic honeycomb or cubic cellulation is the only proper regular space-filling tessellation in Euclidean 3-space made up of cubic cells. It has 4 cubes around every edge, and 8 cubes around each vertex. Its vertex figure is a regular octahedron. It is a self-dual tessellation with Schläfli symbol {4,3,4}. John Horton Conway called this honeycomb a cubille.

The tetrahedral-octahedral honeycomb, alternated cubic honeycomb is a quasiregular space-filling tessellation in Euclidean 3-space. It is composed of alternating regular octahedra and tetrahedra in a ratio of 1:2.

In graph theory, series–parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.

In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs $K 5$ or $K 3,3$ , every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

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 cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

<span class="mw-page-title-main">Italo Jose Dejter</span>

Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

In the mathematical field of graph theory, an antiprism graph is a graph that has one of the antiprisms as its skeleton. An $n$ -sided antiprism has $2 n$ vertices and $4 n$ edges. They are regular, polyhedral, and also Hamiltonian graphs.

References

1 2 3 Weisstein, Eric W. "Prism graph". MathWorld .
↑ Read, R. C. and Wilson, R. J. An Atlas of Graphs, Oxford, England: Oxford University Press, 2004 reprint, Chapter 6 special graphs pp. 261, 270.
↑ Eppstein, David (2013), "The complexity of bendless three-dimensional orthogonal graph drawing", Journal of Graph Algorithms and Applications , 17 (1): 35–55, arXiv: 0709.4087 , doi:10.7155/jgaa.00283, MR 3019198, 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.
↑ Jagers, A. A. (1988), "A note on the number of spanning trees in a prism graph", International Journal of Computer Mathematics, 24 (2): 151–154, doi:10.1080/00207168808803639 .
↑ Marc, Tilen (2015), Classification of vertex-transitive cubic partial cubes, arXiv: 1509.04565 , Bibcode:2015arXiv150904565M .
↑ Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G. (1990), "Forbidden minors characterization of partial 3-trees", Discrete Mathematics, 80 (1): 1–19, doi:10.1016/0012-365X(90)90292-P, MR 1045920 .
↑ Guy, Richard K.; Harary, Frank (1967), "On the Möbius ladders", Canadian Mathematical Bulletin , 10 (4): 493–496, doi: 10.4153/CMB-1967-046-4 , MR 0224499 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[mathworld-1] 1 2 3 Weisstein, Eric W. "Prism graph". MathWorld .

[2] Read, R. C. and Wilson, R. J. An Atlas of Graphs, Oxford, England: Oxford University Press, 2004 reprint, Chapter 6 special graphs pp. 261, 270.

[3] Eppstein, David (2013), "The complexity of bendless three-dimensional orthogonal graph drawing", Journal of Graph Algorithms and Applications , 17 (1): 35–55, arXiv: 0709.4087 , doi:10.7155/jgaa.00283, MR 3019198, 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.

[4] Jagers, A. A. (1988), "A note on the number of spanning trees in a prism graph", International Journal of Computer Mathematics, 24 (2): 151–154, doi:10.1080/00207168808803639 .

[5] Marc, Tilen (2015), Classification of vertex-transitive cubic partial cubes, arXiv: 1509.04565 , Bibcode:2015arXiv150904565M .

[6] Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G. (1990), "Forbidden minors characterization of partial 3-trees", Discrete Mathematics, 80 (1): 1–19, doi:10.1016/0012-365X(90)90292-P, MR 1045920 .

[7] Guy, Richard K.; Harary, Frank (1967), "On the Möbius ladders", Canadian Mathematical Bulletin , 10 (4): 493–496, doi: 10.4153/CMB-1967-046-4 , MR 0224499 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]