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,5

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.

References

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

Links

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

Brendan McKay and Adolfo Piperno, nauty

James Trimble, Bute

Wikipedia, Tree-depth

Example

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;
  ...

Crossrefs

Row sums are A000088.

Cf. A263294.

Sequence in context: A305882 A339285 A363043 * A192404 A373746 A291261

Adjacent sequences: A387043 A387044 A387045 * A387047 A387048 A387049

Keyword

nonn,tabl

Author

Kolja Kühn, Aug 14 2025

Status

approved