cp's OEIS Frontend

A387046 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n vertices and treedepth k.

%I A387046 #9 Aug 19 2025 19:30:52
%S A387046 1,1,1,1,2,1,1,4,5,1,1,6,16,10,1,1,10,47,75,22,1,1,14,129,466,386,47,
%T A387046 1,1,21,332,2751,6512,2615,113,1,1,29,816,14298,96913,138336,23982,
%U A387046 292,1,1,41,1951,68951,1159664,5804406,4652868,316417,868,1,1,55,4557,318789,12070626,170635411,580118945,249848040,5998477,2962,1
%N A387046 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n vertices and treedepth k.
%C A387046 The treedepth of a graph is the minimum height of a rooted forest whose closure contains the graph.
%C A387046 It is also the vertex ranking number.
%C A387046 A graph without edges has treedepth 1, any other graph where each connected component is a star or an isolated vertex has treedepth 2.
%C A387046 The complete graph on n vertices has treedepth n.
%C A387046 Values are computed by combining the programs nauty by Brendan McKay and Adolfo Piperno and Bute by James Trimble.
%D A387046 J. Nešetřil and P. Ossona de Mendez, Sparsity: Graphs, Structures, and Algorithms, Springer, 2012.
%H A387046 Brendan McKay and Adolfo Piperno, <a href="https://users.cecs.anu.edu.au/~bdm/nauty/">nauty</a>
%H A387046 James Trimble, <a href="https://github.com/jamestrimble/bute">Bute</a>
%H A387046 Wikipedia, <a href="http://en.wikipedia.org/wiki/Tree-depth">Tree-depth</a>
%e A387046 Triangle begins:
%e A387046   1;
%e A387046   1, 1;
%e A387046   1, 2, 1;
%e A387046   1, 4, 5, 1;
%e A387046   1, 6, 16, 10, 1;
%e A387046   1, 10, 47, 75, 22, 1;
%e A387046   1, 14, 129, 466, 386, 47, 1;
%e A387046   1, 21, 332, 2751, 6512, 2615, 113, 1;
%e A387046   1, 29, 816, 14298, 96913, 138336, 23982, 292, 1;
%e A387046   1, 41, 1951, 68951, 1159664, 5804406, 4652868, 316417, 868, 1;
%e A387046   1, 55, 4557, 318789, 12070626, 170635411, 580118945, 249848040, 5998477, 2962, 1;
%e A387046   ...
%Y A387046 Row sums are A000088.
%Y A387046 Cf. A263294.
%K A387046 nonn,tabl
%O A387046 1,5
%A A387046 _Kolja Kühn_, Aug 14 2025