A006785 Number of triangle-free graphs on n vertices.
1, 2, 3, 7, 14, 38, 107, 410, 1897, 12172, 105071, 1262180, 20797002, 467871369, 14232552452, 581460254001, 31720840164950
Offset: 1
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
- CombOS - Combinatorial Object Server, Generate graphs
- P. Erdős, D. J. Kleitman, and B. L. Rothschild, Asymptotic enumeration of k_n-free graphs. In Colloquio Internazionale sulle Teorie Combinatorie, (Rome, 1973), Tomo II, Atti dei Convegni Lincei, No. 17, pp. 19-27. Accad. Naz. Lincei, Rome.
- Jérôme Kunegis, Jun Sun, and Eiko Yoneki, Guided Graph Generation: Evaluation of Graph Generators in Terms of Network Statistics, and a New Algorithm, arXiv:2303.00635 [cs.SI], 2023, p. 17.
- Brendan McKay, Emails to N. J. A. Sloane, 1991
- B. D. McKay, Isomorph-free exhaustive generation, J Algorithms, 26 (1998) 306-324.
- W. Pu, J. Choi, and E. Amir, Lifted Inference On Transitive Relations, Workshops at the Twenty-Seventh AAAI Conference on Statistical Relational Artificial Intelligence, 2013.
- Eric Weisstein's World of Mathematics, Triangle-Free Graph
Formula
Erdős, Kleitman, & Rothschild prove that a(n) = 2^(n^2/4 + o(n^2)) and a(n) = (1 + o(1/n))*A033995(n). - Charles R Greathouse IV, Feb 01 2018
Extensions
2 more terms (from the McKay paper) from Vladeta Jovovic, May 17 2008
2 more terms from Brendan McKay, Jan 12 2013