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

1, 2, 3, 6, 11, 23, 48, 114, 293, 869, 2963, 12066, 58933, 347498, 2455693, 20592932, 202724920, 2322206466, 30743624324, 468026657815, 8161170076257

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• more

Comments

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

References

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

Links

• CombOS - Combinatorial Object Server, Generate graphs
• Brendan McKay, Emails to N. J. A. Sloane, 1991
• Brendan D. McKay, Isomorph-free exhaustive generation, Table 2.
• Brendan D. McKay, Isomorph-Free Exhaustive Generation, J. Algorithms, vol. 26 iss. 2 (1998), 306-324.

Crossrefs

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

Formula

a(n) = A000088(n) - A128236(n) - A128237(n). - Andrew Howroyd, May 06 2021

Extensions

Definition corrected by Brendan McKay, Apr 27 2007

a(18)-a(19) (from the McKay reference) added by R. J. Mathar, Jun 17 2008

a(20)-a(21) from Brendan McKay, Mar 11 2018