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

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

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
• tabf

Comments

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.

Examples

			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)
		

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

Crossrefs

Cf. A077105, A107452-A107460.

Extensions

Example corrected by Greg Demand, Jan 17 2008

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