login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #40 Jan 01 2024 09:11:16

%S 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,

%T 1,75,1639,5889,4163,557,21,1,1,152,9203,81786,138923,42596,1977,29,1

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

%C 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

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000272">The treewidth of a graph</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Treewidth">Treewidth</a>

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 5, 4, 1;

%e 1, 9, 17, 6, 1;

%e 1, 19, 72, 53, 10, 1;

%e 1, 36, 323, 501, 168, 14, 1;

%e 1, 75, 1639, 5889, 4163, 557, 21, 1;

%e 1, 152, 9203, 81786, 138923, 42596, 1977, 29, 1;

%e ...

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

%Y Partial row sums include A000012, A005195, A000041.

%Y Row sums are A000088.

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

%K nonn,tabl,more

%O 1,5

%A _Christian Stump_, Oct 13 2015

%E Corrected and extended by _Martin Rubey_, May 10 2023