cp's OEIS Frontend

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

%I A387431 #4 Sep 03 2025 22:50:39
%S A387431 1,0,1,0,1,1,0,1,4,1,0,1,10,9,1,0,1,25,64,21,1,0,1,62,380,363,46,1,0,
%T A387431 1,137,2196,6103,2567,112,1,0,1,294,10963,89989,135673,23868,291,1,0,
%U A387431 1,599,51051,1055752,5663404,4628772,316124,867,1,0,1,1187,230003,10805643,164689853,575441978,249531330,5997608,2961,1
%N A387431 Triangle read by rows: T(n,k) is the number of unlabeled simple connected graphs with n vertices and treedepth k.
%C A387431 The treedepth of a graph is the minimum height of a rooted forest whose closure contains the graph.
%C A387431 It is also the vertex ranking number.
%C A387431 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 A387431 The complete graph on n vertices has treedepth n.
%C A387431 Values are computed by combining the programs nauty by Brendan McKay and Adolfo Piperno and Bute by James Trimble.
%D A387431 J. Nešetřil and P. Ossona de Mendez, Sparsity: Graphs, Structures, and Algorithms, Springer, 2012.
%H A387431 Brendan McKay and Adolfo Piperno, <a href="https://users.cecs.anu.edu.au/~bdm/nauty/">nauty</a>
%H A387431 James Trimble, <a href="https://github.com/jamestrimble/bute">Bute</a>
%H A387431 Wikipedia, <a href="http://en.wikipedia.org/wiki/Tree-depth">Tree-depth</a>
%e A387431 Triangle begins:
%e A387431   1;
%e A387431   0, 1;
%e A387431   0, 1, 1;
%e A387431   0, 1, 4, 1;
%e A387431   0, 1, 10, 9, 1;
%e A387431   0, 1, 25, 64, 21, 1;
%e A387431   0, 1, 62, 380, 363, 46, 1;
%e A387431   0, 1, 137, 2196, 6103, 2567, 112, 1;
%e A387431   0, 1, 294, 10963, 89989, 135673, 23868, 291, 1;
%e A387431   0, 1, 599, 51051, 1055752, 5663404, 4628772, 316124, 867, 1;
%e A387431   0, 1, 1187, 230003, 10805643, 164689853, 575441978, 249531330, 5997608, 2961, 1;
%e A387431   ...
%Y A387431 Row sums are A001349.
%Y A387431 Cf. A387046 (analogous sequence including disconnected graphs), A263294.
%K A387431 nonn,tabl,new
%O A387431 1,9
%A A387431 _Kolja Kühn_, Aug 29 2025