A216783 Number of maximal triangle-free graphs with n vertices.

1, 1, 1, 2, 3, 4, 6, 10, 16, 31, 61, 147, 392, 1274, 5036, 25617, 164796, 1337848, 13734745, 178587364, 2911304940, 58919069858, 1474647067521, 45599075629687

Offset

1,4

Comments

A maximal triangle-free graph is a triangle-free graph so that the insertion of each new edge introduces a triangle. For graphs of order larger than 2 this is equivalent to being triangle-free and having diameter 2.

References

S. Brandt, G. Brinkmann and T. Harmuth, The Generation of Maximal Triangle-Free Graphs, Graphs and Combinatorics, 16 (2000), 149-157.

Links

Table of n, a(n) for n=1..24.

S. Brandt, G. Brinkmann and T. Harmuth, MTF.

Gunnar Brinkmann, Jan Goedgebeur and J.C. Schlage-Puchta, triangleramsey.

Gunnar Brinkmann, Jan Goedgebeur, and Jan-Christoph Schlage-Puchta, Ramsey numbers R(K3,G) for graphs of order 10, arXiv 1208.0501 (2012).

Jan Goedgebeur, On minimal triangle-free 6-chromatic graphs, arXiv:1707.07581 [math.CO] (2017).

House of Graphs, Maximal triangle-free graphs.

Crossrefs

Cf. A280020 (labeled graphs).

Sequence in context: A352946 A342759 A293632 * A026502 A060163 A106511

Adjacent sequences: A216780 A216781 A216782 * A216784 A216785 A216786

Keyword

nonn

Author

Jan Goedgebeur, Sep 18 2012

Extensions

a(24) added by Jan Goedgebeur, Jun 05 2018

Status

approved