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

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

Offset

2,1

Comments

Previous name was: Ramsey numbers.

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.

The terms a(10), a(11) and a(12) were calculated by Harborth and Krause. - Jörgen Backelin, Jan 07 2016

References

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

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

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

Links

Table of n, a(n) for n=2..12.

J. G. Kalbfleisch, Construction of special edge-chromatic graphs, Canad. Math. Bull., 8 (1965), 575-584.

Example

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

Crossrefs

Cf. A000791.

Sequence in context: A354007 A004711 A291922 * A178752 A225255 A076145

Adjacent sequences: A000786 A000787 A000788 * A000790 A000791 A000792

Keyword

nonn,hard,more

Author

N. J. A. Sloane

Extensions

New title and a(10), a(11), a(12) added by Jörgen Backelin, Jan 12 2016

Status

approved