login
Maximal order of a triangle-free cyclic graph with no independent set of size n.
(Formerly M1347 N0516)
1

%I M1347 N0516 #46 Dec 19 2021 09:46:31

%S 2,5,8,13,16,21,26,35,38,45,48

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

%C Previous name was: Ramsey numbers.

%C 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 The terms a(10), a(11) and a(12) were calculated by Harborth and Krause. - _Jörgen Backelin_, Jan 07 2016

%D H. Harborth, S. Krause: Ramsey Numbers for Circulant Colorings, Congressus Numerantium 161 (2003), pp. 139-150.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H 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 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 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 Thus, indeed, a(6) = 16.

%Y Cf. A000791.

%K nonn,hard,more

%O 2,1

%A _N. J. A. Sloane_

%E New title and a(10), a(11), a(12) added by _Jörgen Backelin_, Jan 12 2016