A263294 Triangle read by rows: T(n,k) is the number of graphs with n vertices and treewidth k.

1, 1, 1, 1, 2, 1, 1, 5, 4, 1, 1, 9, 17, 6, 1, 1, 19, 72, 53, 10, 1, 1, 36, 323, 501, 168, 14, 1, 1, 75, 1639, 5889, 4163, 557, 21, 1, 1, 152, 9203, 81786, 138923, 42596, 1977, 29, 1

Offset

1,5

Comments

A graph without edges has treewidth 0, any other forest has treewidth 1, any other series parallel graph has treewidth 2. - Martin Rubey, May 10 2023

Links

Table of n, a(n) for n=1..45.

FindStat - Combinatorial Statistic Finder, The treewidth of a graph.

Wikipedia, Treewidth

Example

Triangle begins:
  1;
  1,   1;
  1,   2,    1;
  1,   5,    4,     1;
  1,   9,   17,     6,      1;
  1,  19,   72,    53,     10,     1;
  1,  36,  323,   501,    168,    14,    1;
  1,  75, 1639,  5889,   4163,   557,   21,  1;
  1, 152, 9203, 81786, 138923, 42596, 1977, 29, 1;
  ...

Crossrefs

Columns k=2..3 are A362908, A362907.

Partial row sums include A000012, A005195, A000041.

Row sums are A000088.

T(n,n-2) = A000065(n).

Sequence in context: A288620 A263324 A284949 * A241500 A152924 A220738

Adjacent sequences: A263291 A263292 A263293 * A263295 A263296 A263297

Keyword

nonn,tabl,more

Author

Christian Stump, Oct 13 2015

Extensions

Corrected and extended by Martin Rubey, May 10 2023

Status

approved