A181170 - OEIS

%I #27 Jun 18 2017 10:12:09

%S 1,0,0,0,0,0,0,0,0,1,1,14

%N Number of connected 9-regular simple graphs on 2n vertices with girth at least 4.

%C a(11)=14 was computed by the author using GENREG at U. Ncle. over 615 processor days during Dec 2009.

%H Jason Kimberley, <a href="/wiki/User:Jason_Kimberley/C_girth_ge_4">Connected regular graphs with girth at least 4</a>

%H Jason Kimberley, <a href="/wiki/User:Jason_Kimberley/C_k-reg_girth_ge_g_index">Index of sequences counting connected k-regular simple graphs with girth at least g</a>

%H M. Meringer, <a href="http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html">Tables of Regular Graphs</a>

%H M. Meringer, <a href="http://dx.doi.org/10.1002/(SICI)1097-0118(199902)30:2&lt;137::AID-JGT7&gt;3.0.CO;2-G">Fast generation of regular graphs and construction of cages</a>, J. Graph Theory 30 (2) (1999) 137-146.

%e The a(0)=1 null graph is vacuously 8-regular and connected; since it is acyclic then it has infinite girth.

%e The a(9)=1 graph is the complete bipartite graph K_{9,9} with 18 vertices.

%e The a(10)=1 graph has girth 4, automorphism group of order 7257600, and the following adjacency lists:

%e 01 : 02 03 04 05 06 07 08 09 10

%e 02 : 01 11 12 13 14 15 16 17 18

%e 03 : 01 11 12 13 14 15 16 17 19

%e 04 : 01 11 12 13 14 15 16 18 19

%e 05 : 01 11 12 13 14 15 17 18 19

%e 06 : 01 11 12 13 14 16 17 18 19

%e 07 : 01 11 12 13 15 16 17 18 19

%e 08 : 01 11 12 14 15 16 17 18 19

%e 09 : 01 11 13 14 15 16 17 18 19

%e 10 : 01 12 13 14 15 16 17 18 19

%e 11 : 02 03 04 05 06 07 08 09 20

%e 12 : 02 03 04 05 06 07 08 10 20

%e 13 : 02 03 04 05 06 07 09 10 20

%e 14 : 02 03 04 05 06 08 09 10 20

%e 15 : 02 03 04 05 07 08 09 10 20

%e 16 : 02 03 04 06 07 08 09 10 20

%e 17 : 02 03 05 06 07 08 09 10 20

%e 18 : 02 04 05 06 07 08 09 10 20

%e 19 : 03 04 05 06 07 08 09 10 20

%e 20 : 11 12 13 14 15 16 17 18 19

%Y 9-regular simple graphs with girth at least 4: this sequence (connected), A185294 (disconnected).

%Y Connected k-regular simple graphs with girth at least 4: A186724 (any k), A186714 (triangle); specified degree k: A185114 (k=2), A014371 (k=3), A033886 (k=4), A058275 (k=5), A058276 (k=6), A181153 (k=7), A181154 (k=8), this sequence (k=9).

%Y Connected 9-regular simple graphs with girth at least g: A014378 (g=3), this sequence (g=4).

%Y Connected 9-regular simple graphs with girth exactly g: A184993 (g=3).

%K nonn,more,hard

%O 0,12

%A _Jason Kimberley_, last week of Jan 2011