login
Number of n-node graphs with no cycles of length less than 5.
(Formerly M0792)
9

%I M0792 #47 Nov 19 2021 17:41:05

%S 1,2,3,6,11,23,48,114,293,869,2963,12066,58933,347498,2455693,

%T 20592932,202724920,2322206466,30743624324,468026657815,8161170076257

%N Number of n-node graphs with no cycles of length less than 5.

%C Includes graphs with no cycles at all as well as graphs with girth greater than 5.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H CombOS - Combinatorial Object Server, <a href="http://combos.org/nauty">Generate graphs</a>

%H Brendan McKay, <a href="/A006785/a006785.pdf">Emails to N. J. A. Sloane, 1991</a>

%H Brendan D. McKay, <a href="https://users.cecs.anu.edu.au/people/Brendan.McKay/papers/orderly.pdf">Isomorph-free exhaustive generation</a>, Table 2.

%H Brendan D. McKay, <a href="http://dx.doi.org/10.1006/jagm.1997.0898">Isomorph-Free Exhaustive Generation</a>, J. Algorithms, vol. 26 iss. 2 (1998), 306-324.

%F a(n) = A000088(n) - A128236(n) - A128237(n). - _Andrew Howroyd_, May 06 2021

%Y Cf. A000066, A000088, A054760, A159847, A126757 (connected, inv. Eul. Transf.), A128236, A128237, A300705.

%K nonn,more

%O 1,2

%A _N. J. A. Sloane_

%E Definition corrected by _Brendan McKay_, Apr 27 2007

%E a(18)-a(19) (from the McKay reference) added by _R. J. Mathar_, Jun 17 2008

%E a(20)-a(21) from _Brendan McKay_, Mar 11 2018