A336194 - OEIS

A336194

Table read by antidiagonals upwards: T(n,k) = (n - 1)*k^3 - 1, with n > 1 and k > 0.

0, 1, 7, 2, 15, 26, 3, 23, 53, 63, 4, 31, 80, 127, 124, 5, 39, 107, 191, 249, 215, 6, 47, 134, 255, 374, 431, 342, 7, 55, 161, 319, 499, 647, 685, 511, 8, 63, 188, 383, 624, 863, 1028, 1023, 728, 9, 71, 215, 447, 749, 1079, 1371, 1535, 1457, 999, 10, 79, 242, 511, 874, 1295, 1714, 2047, 2186, 1999, 1330

(list; table; graph; refs; listen; history; text; internal format)

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

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

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.

Index entries for sequences related to trees.

FORMULA

O.g.f.: x^2*y*(y*(7 - 2*y + y^2) + x*(1 - y)^3)/((1 - x)^2*(1 - y)^4).

E.g.f.: -1 + exp(x) - x + exp(y)*x + exp(y)*(1 + y + 3*y^2 + y^3) + exp(x + y)*(-1 +(-1 + x)*y*(1 + 3*y + y^2)).

T(n, k) = n*A000578(k) - A001093(k).

T(n, n) = A085537(n) - 1 for n > 1.

T(n, k) = T(n+1, 1)*T(2, k) + T(n, 1).

EXAMPLE