login
Number of trivalent connected simple graphs with 2n nodes and girth at least 4.
27

%I #49 Aug 04 2024 05:35:52

%S 1,0,0,1,2,6,22,110,792,7805,97546,1435720,23780814,432757568,

%T 8542471494,181492137812,4127077143862

%N Number of trivalent connected simple graphs with 2n nodes and girth at least 4.

%C The null graph on 0 vertices is vacuously connected and 3-regular; since it is acyclic, it has infinite girth. [_Jason Kimberley_, Jan 29 2011]

%D CRC Handbook of Combinatorial Designs, 1996, p. 647.

%H G. Brinkmann, J. Goedgebeur and B. D. McKay, <a href="https://hal.archives-ouvertes.fr/hal-00990486">Generation of Cubic graphs</a>, Discrete Mathematics and Theoretical Computer Science, 13 (2) (2011), 69-80. (hal-00990486)

%H House of Graphs, <a href="https://houseofgraphs.org/meta-directory/cubic">Cubic graphs</a>.

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

%t A[s_Integer] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import["https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {_, _}][[All, 2]]];

%t A002851 = A@002851;

%t A006923 = A@006923;

%t a[n_] := A002851[[n + 1]] - A006923[[n + 1]];

%t a /@ Range[0, 16] (* _Jean-François Alcover_, Jan 27 2020 *)

%Y Contribution from _Jason Kimberley_, Jun 28 2010 and Jan 29 2011: (Start)

%Y 3-regular simple graphs with girth at least 4: this sequence (connected), A185234 (disconnected), A185334 (not necessarily connected).

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

%Y Connected 3-regular simple graphs with girth at least g: A185131 (triangle); chosen g: A002851 (g=3), this sequence (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).

%Y Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7). (End)

%K nonn,nice,more,hard

%O 0,5

%A _N. J. A. Sloane_

%E Terms a(14) and a(15) appended, from running Meringer's GENREG for 4.2 and 93.2 processor days at U. Newcastle, by Jason Kimberley on Jun 28 2010.

%E a(16), from House of Graphs, by Jan Goedgebeur et al., added by _Jason Kimberley_, Feb 15 2011