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

Author

Jan Goedgebeur, Sep 18 2012

Keywords

• nonn

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

• 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).

Extensions

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