

A000789


Maximal order of a trianglefree cyclic graph with no independent set of size n.
(Formerly M1347 N0516)


1



2, 5, 8, 13, 16, 21, 26, 35, 38, 45, 48
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 twocolor 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. 139150.
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 edgechromatic graphs, Canad. Math. Bull., 8 (1965), 575584.


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 trianglefree 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: A053614 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



