OFFSET
2,3
COMMENTS
T(n, k) is a sharp upper bound of the tree width of a graph G that does not contain a clique on n vertices nor a minimal separator of size larger than k (see Theorem 2.1 in Pilipczuk et al.).
All the square matrices starting at top left of the table T are singular except for the 2 X 2 submatrix: det([0, 7; 1, 15]) = -7.
LINKS
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé and Nicolas Trotignon, (Theta, triangle)-free and (even hole, K4)-free graphs. Part 2 : bounds on treewidth, arXiv:2001.01607 [cs.DM], 2020. See p. 7.
FORMULA
EXAMPLE
The table starts at row n = 2 and column k = 1 as:
0 7 26 63 124 215 ...
1 15 53 127 249 431 ...
2 23 80 191 374 647 ...
3 31 107 255 499 863 ...
4 39 134 319 624 1079 ...
5 47 161 383 749 1295 ...
...
MATHEMATICA
T[n_, k_]:=(n-1)*k^3-1; Flatten[Table[T[n+1-k, k], {n, 2, 12}, {k, 1, n-1}]]
PROG
(PARI) T(n, k) = (n - 1)*k^3 - 1
CROSSREFS
KEYWORD
AUTHOR
Stefano Spezia, Jul 11 2020
STATUS
approved