OFFSET
4,5
COMMENTS
Number of nonisomorphic generalized Petersen graphs P(n,k) with girth 4 on 2n vertices for 1 <= k <= floor((n-1)/2).
The generalized Petersen graph P(n,k) is a graph with vertex set V(P(n,k)) = {u_0,u_1,...,u_{n-1},v_0,v_1,...,v_{n-1}} and edge set E(P(n,k)) = {u_i u_{i+1}, u_i v_i, v_i v_{i+k} : i=0,...,n-1}, where the subscripts are to be read modulo n.
Also the number of nonisomorphic bipartite generalized Petersen graphs P(2n,k) with girth 4 on 4n vertices for 1 <= k < n, n >= 2. A generalized Petersen graph P(n,k) is bipartite if and only if n is even and k is odd; it has girth 4 if and only if n = 4*k or k = 1.
From Tomaz Pisanski, Mar 08 2008: (Start)
The fact that the two interpretations give the same numerical values is a coincidence.
Let f(n) be the number of generalized Petersen graphs P(n,k), n = 4,5,... of girth 4. Let g(n) be the number of bipartite generalized Petersen graphs P(2n,k), n = 2,3,4,... of girth 4.
The sequences may be computed as follows: f(t) = if t = 4 then 1 else if 4|t then 2 else 1 and g(s) = if s = 2 then else if mod(s,4) = 2 then 2 else 1. It follows that f(n+2) = g(n).
The exception f(4) = g(2) = 1 does count the same object, namely, P(4,1) but for all other cases f(n+2) counts different objects that g(n). (End)
Continued fraction expansion of sqrt(8/3), if the offset is 1. - Arkadiusz Wesolowski, Aug 27 2011
REFERENCES
I. Z. Bouwer, W. W. Chernoff, B. Monson, and Z. Star, The Foster Census, R. M. Foster's Census of Connected Symmetric Trivalent Graphs, Charles Babbage Research Centre, 1988, ISBN 0-919611-19-2.
LINKS
Marko Boben, Tomaz Pisanski and Arjana Zitnik, I-graphs and the corresponding configurations, Preprint series (University of Ljubljana, IMFM), Vol. 42 (2004), 939 (ISSN 1318-4865).
Mark E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory, Vol. 6, No. 2 (1969), 152-164.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,1).
FORMULA
a(n) = denominator((n+1)*(n+2)*(n+3)/12) for n >= 5. - Eric W. Weisstein, Mar 04 2008
a(n) = sgn(n) + cos(Pi*n/4)^2 + (cos(Pi*n)-1)/4; a(n) = sgn(n) + floor(((n+3) mod 4)/3). - Carl R. White, Oct 15 2009
From Colin Barker, Jul 16 2013: (Start)
a(n) = (5+(-1)^n+(-i)^n+i^n)/4 for n>4, where i=sqrt(-1).
G.f.: -x^4*(x^4+x^3+x^2+x+1) / ((x-1)*(x+1)*(x^2+1)). (End)
E.g.f.: sinh(x) + 3*cosh(x)/2 + cos(x)/2 - 2 - x - x^2/2 - x^3/6 - x^4/24. - Amiram Eldar, Nov 29 2025
EXAMPLE
A generalized Petersen graph P(n,k) has girth 4 if and only if n = 4*k or k = 1.
The smallest generalized Petersen graph with girth 4 is P(4,1).
The smallest bipartite generalized Petersen graph with girth 4 is P(4,1).
MATHEMATICA
Join[{1, 1, 1}, Table[Denominator[(n - 1) n (n + 1)/12], {n, 100}]] (* Eric W. Weisstein, Mar 04 2008 *)
Join[{1}, PadRight[{}, 104, {1, 1, 1, 2}]] (* Harvey P. Dale, Oct 25 2011 *)
PROG
(PARI) my(x='x+O('x^100)); Vec(-x^4*(x^4+x^3+x^2+x+1)/((x-1)*(x+1)*(x^2+1))) \\ Altug Alkan, Dec 24 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Marko Boben (Marko.Boben(AT)fmf.uni-lj.si), Tomaz Pisanski and Arjana Zitnik (Arjana.Zitnik(AT)fmf.uni-lj.si), May 26 2005
EXTENSIONS
Edited by N. J. A. Sloane, Mar 08 2008
STATUS
approved