A107460 -id:A107460 - cp's OEIS frontend

A107452 Number of nonisomorphic bipartite generalized Petersen graphs P(2n,k) on 4n vertices for 1<=k

1, 1, 2, 2, 3, 2, 3, 3, 4, 3, 6, 4, 5, 6, 5, 5, 7, 5, 8, 8, 7, 6, 10, 8, 8, 9, 10, 8, 13, 8, 9, 12, 10, 12, 14, 10, 11, 14, 14, 11, 17, 11, 14, 17, 13, 12, 18, 14, 16

Offset: 2

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

nonn

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.

			A generalized Petersen graph P(n,k) is bipartite if and only if n is even and k is odd.
The smallest bipartite generalized Petersen graph is P(4,1)

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

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).
B. Horvat, T. Pisanski; A. Zitnik. Isomorphism checking of I-graphs, Graphs Comb. 28, No. 6, 823-830 (2012).
M. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969), 152-164.

Cf. A077105, A107453-A107460.

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

Original entry on oeis.org

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

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

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

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

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

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

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

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

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

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)

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

A107459 Number of nonisomorphic bipartite generalized Petersen graphs P(2n,k) with girth 6 on 4n vertices for 1<=k

Original entry on oeis.org

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

Offset: 4

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

nonn

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.

			A generalized Petersen graph P(n,k) is bipartite if and only if n is even and k is odd; it has girth 6 if and only if it has girth more than 4 and (n=6k or k=3 or 2k=n-2 or 3k=n+1 or 3k=n-1)
The smallest bipartite generalized Petersen graph with girth 6 is P(8,3)

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

Marko Boben, Tomaz Pisanski, 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.

Cf. A077105, A107452-A107460.

A107454 Number of nonisomorphic generalized Petersen graphs P(n,k) with girth 5 on 2n vertices for 1<=k<=Floor[(n-1)/2].

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1

Offset: 5

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

nonn

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.

			A generalized Petersen graph P(n,k) has girth 5 if and only if it has girth more than 4 and (n=5k or 2n=5k or k=2 or 2k=n-1).
The smallest generalized Petersen graph with girth 5 is P(5,2)

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

Marko Boben, Tomaz Pisanski, 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.

Cf. A077105, A107452-A107460.

A107457 Triangle read by rows: row n gives number of nonisomorphic generalized Petersen graphs P(n,k) with girth 8 on n vertices for 1<=k<=floor[(n-1)/2].

Original entry on oeis.org

1, 0, 0, 1, 2, 1, 4, 1, 4, 3, 2, 3, 4, 3, 5, 6, 7, 2, 7, 5, 8, 8, 8, 6, 8, 6, 10, 9, 11, 7, 13, 6, 12, 12, 13, 9, 15, 11, 13, 14, 16, 10, 17, 11, 17, 14, 17, 15, 21, 12, 19, 18, 18, 13, 23, 14, 22, 20, 22, 16, 26, 15, 24, 21, 25, 16, 26, 21, 26, 24

Offset: 18

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

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.

			Any generalized Petersen graph P(n,k) has girth at most 8; it has girth 8 if and only if it has girth more than 7.
The smallest generalized Petersen graph with girth 8 is P(18,5)

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

Marko Boben, Tomaz Pisanski, Arjana Zitnik, I-graphs and the corresponding configurations, Preprint series (University of Ljubljana, IMFM), Vol. 42 (2004), 939 (ISSN 1318-4865).
B. Horvat, T. Pisanski; A. Zitnik. Isomorphism checking of I-graphs, Graphs Comb. 28, No. 6, 823-830 (2012).
M. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969), 152-164.

Cf. A077105, A107452-A107460.

Example corrected by Greg Demand, Jan 17 2008

Typo in description corrected by Harvey P. Dale, Aug 17 2020

A107455 Number of nonisomorphic generalized Petersen graphs P(n,k) with girth 6 on n vertices for 1<=k<=Floor[(n-1)/2].

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 0, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3

Offset: 8

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

nonn

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.

			A generalized Petersen graph P(n,k) has girth 6 if and only if it has girth more than 5 and (n=6k or k=3 or 2k=n-2 or 3k=n+1 or 3k=n-1)
The smallest generalized Petersen graph with girth 6 is P(8,3)

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

Marko Boben, Tomaz Pisanski, 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.

Cf. A077105, A107452-A107460.

A107456 Number of nonisomorphic generalized Petersen graphs P(n,k) with girth 7 on n vertices for 1<=k<=Floor[(n-1)/2].

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 0, 2, 2, 2, 4, 2, 1, 2, 2, 2, 2, 5, 1, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 1, 5, 2, 2, 2, 2, 1, 2, 5, 2, 2, 2, 1, 2, 2, 5, 2, 2, 1, 2, 2, 2, 5, 2, 1, 2, 2, 2, 2, 5, 1, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 1, 5, 2, 2, 2, 2, 1, 2, 5, 2, 2

Offset: 13

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

nonn

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.

			A generalized Petersen graph P(n,k) has girth 7 if and only if it has girth more than 6 and (n=7k or 2n=7*k or 3n=7k or k=4 or 4k=n+1 or 4=n-k or 4k=n-1 or 4k=2n-1 or 3k=n+2 or 3=n-2k or 3k=n-2)
The smallest generalized Petersen graph with girth 7 is P(13,5)

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

Marko Boben, Tomaz Pisanski, 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.

Cf. A077105, A107452-A107460.

cp's OEIS Frontend

A107452 Number of nonisomorphic bipartite generalized Petersen graphs P(2n,k) on 4n vertices for 1<=k

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A107459 Number of nonisomorphic bipartite generalized Petersen graphs P(2n,k) with girth 6 on 4n vertices for 1<=k

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A107454 Number of nonisomorphic generalized Petersen graphs P(n,k) with girth 5 on 2n vertices for 1<=k<=Floor[(n-1)/2].

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A107457 Triangle read by rows: row n gives number of nonisomorphic generalized Petersen graphs P(n,k) with girth 8 on n vertices for 1<=k<=floor[(n-1)/2].

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A107455 Number of nonisomorphic generalized Petersen graphs P(n,k) with girth 6 on n vertices for 1<=k<=Floor[(n-1)/2].

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A107456 Number of nonisomorphic generalized Petersen graphs P(n,k) with girth 7 on n vertices for 1<=k<=Floor[(n-1)/2].

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs