Antiprism Graph
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 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.
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
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, Prism GraphExplore with Wolfram|Alpha
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.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 GraphCite this as:
Weisstein, Eric W. "Antiprism Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AntiprismGraph.html