cp's OEIS Frontend

A000789 Maximal order of a triangle-free cyclic graph with no independent set of size n.

%I A000789 M1347 N0516 #46 Dec 19 2021 09:46:31
%S A000789 2,5,8,13,16,21,26,35,38,45,48
%N A000789 Maximal order of a triangle-free cyclic graph with no independent set of size n.
%C A000789 Previous name was: Ramsey numbers.
%C A000789 The sequence may be considered as consisting of a special kind of Ramsey numbers. It is related to the ordinary two-color Ramsey numbers R(3,n), given in A000791, by the relation a(n) <= A000791(n)-1 as proved by Kalbfleisch. He also calculated the first eight terms, and noted that the inequality sometimes is strict. The first n for which this happens is n=6.
%C A000789 The terms a(10), a(11) and a(12) were calculated by Harborth and Krause. - _Jörgen Backelin_, Jan 07 2016
%D A000789 H. Harborth, S. Krause: Ramsey Numbers for Circulant Colorings, Congressus Numerantium 161 (2003), pp. 139-150.
%D A000789 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000789 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000789 J. G. Kalbfleisch, <a href="http://dx.doi.org/10.4153/CMB-1965-041-7">Construction of special edge-chromatic graphs</a>, Canad. Math. Bull., 8 (1965), 575-584.
%e A000789 That a(6) >= 16 is seen from the cyclic (or circulant) graph on 16 vertices, with edges between vertices of index distances 1, 3, or 8, since this cyclic graph indeed is triangle-free and has independence number five, which is less than six.
%e A000789 On the other hand, a(6) < 17, since any triangle free graph with independence number less than six and at least 17 vertices has exactly 17 vertices and cannot be regular, but all cyclic graphs are regular.
%e A000789 Thus, indeed, a(6) = 16.
%Y A000789 Cf. A000791.
%K A000789 nonn,hard,more
%O A000789 2,1
%A A000789 _N. J. A. Sloane_
%E A000789 New title and a(10), a(11), a(12) added by _Jörgen Backelin_, Jan 12 2016