mathworld.wolfram.com

Antiprism Graph -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
  • ️Sun Sep 29 2002
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

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

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