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

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

Keywords

• nonn
• easy

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= 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

Examples

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

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

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

Crossrefs

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

Programs

Mathematica

Join[{1},PadRight[{},104,{1,1,1,2}]] (* Harvey P. Dale, Oct 25 2011 *)

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

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)

Extensions

Edited by N. J. A. Sloane, Mar 08 2008