TOPICS
Search

Antiprism Graph


AntiprismGraphs

An antiprism graph is a graph corresponding to the skeleton of an antiprism. Antiprism graphs are therefore polyhedral and planar. The n-antiprism graph has 2n vertices and 4n edges, and is isomorphic to the circulant graph Ci_(2n)(1,2). The 3-antiprism graph is also isomorphic to the octahedral graph.

The graph square of the n-Möbius ladder M_n is the circulant graph Ci_(2n)(1,2,3,4) and its graph cube is Ci_(2n)(1,2,3,4,5,6).

Precomputed properties for antiprism graphs are implemented in the Wolfram Language as GraphData[{"Antiprism", n}].

The numbers of directed Hamiltonian cycles for n=3, 4, ... are 32, 58, 112, 220, 450, 938, 1982, ... (OEIS A124353), whose terms are given by the recurrence relation

 a_n=3a_(n-1)-a_(n-2)-2a_(n-3)+a_(n-5)
(1)

or

 a_n=2a_(n-1)+a_(n-2)-a_(n-3)-a_(n-4)-12
(2)

(Golin and Leung 2004; M. Alekseyev, pers. comm., Feb. 7, 2008), which has the closed-form solution

 a_n=2(2n+alpha^n+beta^n+gamma^n),
(3)

where alpha, beta, and gamma are the roots of x^3-x^2-2x-1=0.

The antiprism graphs are pancyclic. n-antiprism graphs are nut graphs when n is not divisible by 3.

AntiprismGraphCycles3

The numbers of graph cycles on the n-antiprism graph for n=3, 4, ... are 63, 179, 523, ... (OEIS A077263), illustrated above for n=3.

The n-antiprism graph has chromatic polynomial

 pi(x)=2^(-n)(x-1)(s^n+t^n)+(x-2)^(2n)+(x-3)x+1
(4)

where

s=5-2x-sqrt(9-4x)
(5)
t=5-2x+sqrt(9-4x).
(6)

The recurrence relations for the chromatic polynomial, independence polynomial, and matching polynomial are

 pi_n(z)=(z^2-6z+10)pi_(n-1)(z)+(z-3)(2z^2-9z+11)pi_(n-2)(z)+(z^2-6z+10)(z-2)^2pi_(n-3)(z)-(z-2)^4pi_(n-4)(z) 
I_n(x)=x^2I_n-3(x)+2xI_n-2(x)+I_n-1(x) 
mu_n(x)=(x-2)^2mu_(n-1)(x)-(2x^2-1)mu_(n-2)(x)+(x^2+2)mu_(n-3)(x)-mu_(n-4)(x).
(7)

The 6-antiprism graph is cospectral with the quartic vertex-transitive graph Qt19, meaning neither is determined by spectrum.


See also

Antiprism, Circulant Graph, Cospectral Graphs, Determined by Spectrum, Möbius Ladder, Prism Graph

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Golin, M. J. and Leung, Y. C. "Unhooking Circulant Graphs: a Combinatorial Method for Counting Spanning Trees and Other Parameters." In Graph-Theoretic Concepts in Computer Science. Revised Papers from the 30th International Workshop (WG 2004) Held in Bad Honnef, June 21-23, 2004 (Ed. J. Hromkovič, M. Nagl, and B. Westfechtel). Berlin: Springer-Verlag, pp. 296-307, 2004.House of Graphs. Antiprism Graphs. Octahedron K2,2,2, Square of C8, Circulant C10 (1,2), Square of C12, and Circulant Ci20 (1,2).Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 263 and 270, 1998.Sloane, N. J. A. Sequences A077263 and A124353 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Antiprism Graph

Cite this as:

Weisstein, Eric W. "Antiprism Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AntiprismGraph.html

Subject classifications