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

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, 1, 1, 21, 332, 2751, 6512, 2615, 113, 1, 1, 29, 816, 14298, 96913, 138336, 23982, 292, 1, 1, 41, 1951, 68951, 1159664, 5804406, 4652868, 316417, 868, 1, 1, 55, 4557, 318789, 12070626, 170635411, 580118945, 249848040, 5998477, 2962, 1

Offset: 1

Author

Kolja Kühn, Aug 14 2025

Keywords

• nonn
• tabl

Comments

The treedepth of a graph is the minimum height of a rooted forest whose closure contains the graph.

It is also the vertex ranking number.

A graph without edges has treedepth 1, any other graph where each connected component is a star or an isolated vertex has treedepth 2.

The complete graph on n vertices has treedepth n.

Values are computed by combining the programs nauty by Brendan McKay and Adolfo Piperno and Bute by James Trimble.

Examples

			Triangle begins:
  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, 1;
  1, 21, 332, 2751, 6512, 2615, 113, 1;
  1, 29, 816, 14298, 96913, 138336, 23982, 292, 1;
  1, 41, 1951, 68951, 1159664, 5804406, 4652868, 316417, 868, 1;
  1, 55, 4557, 318789, 12070626, 170635411, 580118945, 249848040, 5998477, 2962, 1;
  ...
		

References

• J. Nešetřil and P. Ossona de Mendez, Sparsity: Graphs, Structures, and Algorithms, Springer, 2012.

Links

• Brendan McKay and Adolfo Piperno, nauty
• James Trimble, Bute
• Wikipedia, Tree-depth

Crossrefs

Row sums are A000088.

Cf. A263294.