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

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, 1, 137, 2196, 6103, 2567, 112, 1, 0, 1, 294, 10963, 89989, 135673, 23868, 291, 1, 0, 1, 599, 51051, 1055752, 5663404, 4628772, 316124, 867, 1, 0, 1, 1187, 230003, 10805643, 164689853, 575441978, 249531330, 5997608, 2961, 1

Offset

1,9

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;
  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, 1, 137, 2196, 6103, 2567, 112, 1;
  0, 1, 294, 10963, 89989, 135673, 23868, 291, 1;
  0, 1, 599, 51051, 1055752, 5663404, 4628772, 316124, 867, 1;
  0, 1, 1187, 230003, 10805643, 164689853, 575441978, 249531330, 5997608, 2961, 1;
  ...

Crossrefs

Row sums are A001349.

Cf. A387046 (analogous sequence including disconnected graphs), A263294.

Sequence in context: A363044 A086329 A294118 * A343648 A359363 A381512

Adjacent sequences: A387428 A387429 A387430 * A387432 A387433 A387434

Keyword

nonn,tabl

Author

Kolja Kühn, Aug 29 2025

Status

approved