|
| |
|
|
A198787
|
|
Triangle read by rows: T(n,k) is the number of edges in the (n,k)-Turán graph.
|
|
1
|
|
|
|
0, 0, 1, 0, 2, 3, 0, 4, 5, 6, 0, 6, 8, 9, 10, 0, 9, 12, 13, 14, 15, 0, 12, 16, 18, 19, 20, 21, 0, 16, 21, 24, 25, 26, 27, 28, 0, 20, 27, 30, 32, 33, 34, 35, 36, 0, 25, 33, 37, 40, 41, 42, 43, 44, 45, 0, 30, 40, 45, 48, 50, 51, 52, 53, 54, 55, 0, 36, 48, 54, 57, 60, 61, 62, 63, 64, 65, 66, 0, 42
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
The (n,k)-Turán graph is a complete k-partite graph with n vertices, and all parts of order either floor(n/k) or ceiling(n/k). This graph maximizes the number of edges in any n-vertex graph with no (k+1)-clique.
A193331 is an upper bound on this sequence derived from Turán's theorem. The error term in this upper bound, before rounding, is r(k-r)/(2k), where r = n mod k. This is at most k/8, so in particular, A193331 and this sequence agree for all k < 8. When n=12 and k=8, A193331's upper bound gives 63 and this sequence gives 62. (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = (n^2 - (n mod k)*ceiling(n/k)^2 - (k-n mod k)*floor(n/k)^2)/2.
T(n,k) = (1-1/k)*n^2/2 - r(k-r)/(2k), where r = n mod k. - Mikhail Lavrov, Apr 05 2021
|
|
|
EXAMPLE
|
Triangle begins:
0,
0, 1,
0, 2, 3;
0, 4, 5, 6;
0, 6, 8, 9, 10;
0, 9, 12, 13, 14, 15;
0, 12, 16, 18, 19, 20, 21;
...
The (5,2)-Turán graph is a complete bipartite graph with parts of size 2 and 3. It has 6 edges.
The (12,8)-Turán graph is a complete 8-partite graph with parts of size 2,2,2,2,1,1,1,1. It has 8 vertices of degree 10 and 4 vertices of degree 11, so it has 62 edges.
|
|
|
MATHEMATICA
|
Flatten[Table[(n^2 - Mod[n, k] Ceiling[n/k]^2 - (k - Mod[n, k]) Floor[n/k]^2)/2, {n, 20}, {k, n}]]
Flatten[Table[(1 - 1/k)n^2/2 - (Mod[n, k](k - Mod[n, k]))/(2k), {n, 20}, {k, n}]] (* Mikhail Lavrov, Apr 05 2021 *)
Flatten[Table[EdgeCount[TuranGraph[n, k]], {n, 20}, {k, n}]] (* Mikhail Lavrov, Apr 05 2021 *)
|
|
|
PROG
|
(PARI) T(n, k) = {(n^2 - (n % k)*ceil(n/k)^2 - (k - n % k)*floor(n/k)^2)/2} \\ Andrew Howroyd, Apr 05 2021
|
|
|
CROSSREFS
|
Cf. A193331 (upper bound on this sequence).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
