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 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, Prism Graph

Explore with Wolfram|Alpha

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 Graph

Cite this as:

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

Subject classifications