A107453 1 followed by repetitions of the period-4 sequence 1,1,1,2.

1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2

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 = 4k 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)

Also, Table[Denominator[(n - 1) n (n + 1)/12], {n, 100}] with 3 1's in front... - Eric W. Weisstein, Mar 04 2008

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 (Charles Babbage Research Centre, 1988), ISBN 0-919611-19-2.

Links

Table of n, a(n) for n=4..108.

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).

M. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969), 152-164.

Index entries for linear recurrences with constant coefficients, signature (0,0,0,1).

Formula

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)

Example

A generalized Petersen graph P(n,k) has girth 4 if and only if n = 4k 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}, PadRight[{}, 104, {1, 1, 1, 2}]] (* Harvey P. Dale, Oct 25 2011 *)

Prog

(PARI) 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

Cf. A077105, A107452, A107454-A107457, A107459, A107460.

Sequence in context: A361633 A186006 A236398 * A164115 A164117 A177704

Adjacent sequences: A107450 A107451 A107452 * A107454 A107455 A107456

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