4,5

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,\dots,u_{n-1},v_0,v_1,\dots,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,\dots,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.

Comment 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

I. Z. Bouwer, W. W. Chernoff, B. Monson and Z. Star, The Foster Census (Charles Babbage Research Centre, 1988), ISBN 0-919611-19-2.

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

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

a(n)=(1/24)*{-(n mod 4)+5*[(n+1) mod 4]+5*[(n+2) mod 4]+11*[(n+3) mod 4]}-[C(2*n,n) mod 2], with n>=0 [From Paolo P. Lava (ppl(AT)spl.at), Aug 05 2009]

Contribution from Carl R. White (oeisfan(AT)phodd.net), Oct 15 2009: (Start)

a(n)=sgn(n)+cos(pi*n/4)^2+(cos(pi*n)-1)/4

a(n)=sgn(n)+floor( ((n+3)mod 4)/3 ) (End)

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)

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

Sequence in context: A079211 A081418 A088951 this_sequence A164115 A164117 A138191

Adjacent sequences: A107450 A107451 A107452 this_sequence A107454 A107455 A107456

nonn

Marko Boben (Marko.Boben(AT)fmf.uni-lj.si), Tomaz Pisanski (Tomaz.Pisanski(AT)fmf.uni-lj.si) and Arjana Zitnik (Arjana.Zitnik(AT)fmf.uni-lj.si), May 26 2005

Edited by N. J. A. Sloane (njas(AT)research.att.com), Mar 08 2008