OFFSET
3,1
COMMENTS
The concentric ring graph of order n is a cubic graph with 4n vertices and 6n edges. If we name the vertices a_j,b_j,c_j,d_j for 0<=j<n, the edges are a_j--a_j', a_j--b_j, b_j--c_j, c_j--b_j', c_j--d_j, and d_j--d_j', where j'=(j+1)mod n.
When n=5 it is isomorphic to the graph of the dodecahedron, which Hamilton used when he first considered "Hamiltonian cycles".
REFERENCES
Donald E. Knuth, Prefascicle 8a of The Art of Computer Programming (planned to become part of Volume 4C).
LINKS
Don Knuth, Table of n, a(n) for n = 3..100
Index entries for linear recurrences with constant coefficients, signature (1,1,2,-2,-2,-1,1,1).
FORMULA
a(n) = 2*Lucas(n) - 2 + 2*n*[Mod(n,3)==2], where [ ] denotes the Iverson bracket.
G.f.: -2*x^3*(3+3*x+6*x^2-10*x^3-10*x^4-3*x^5+4*x^6+4*x^7) / ( (x^2+x-1)*(x-1)^2*(1+x+x^2)^2 ). - R. J. Mathar, May 26 2025
EXAMPLE
The a[3]=6 cycles when n=3 are:
a0--a1--a2--b2--c1--b1--c0--d0--d1--d2--c2--b0--a0,
a0--a1--a2--b2--c2--d2--d0--d1--c1--b1--c0--b0--a0,
a0--a1--b1--c0--b0--c2--d2--d0--d1--c1--b2--a2--a0,
a0--a1--b1--c1--d1--d2--d0--c0--b0--c2--b2--a2--a0,
a0--b0--c0--d0--d1--d2--c2--b2--c1--b1--a1--a2--a0,
a0--b0--c2--b2--c1--d1--d2--d0--c0--b1--a1--a2--a0.
MATHEMATICA
a[n_]:=2LucasL[n]-2+If[Mod[n, 3]==2, 2n, 0]; Array[a, 41, 3]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Don Knuth, May 24 2025
STATUS
approved
