|
|
A000789
|
|
Maximal order of a triangle-free 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 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
|
|
|
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
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|