A387046 -id:A387046 - 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.

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

Kolja Kühn, Aug 29 2025

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.

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

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

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

Row sums are A001349.

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

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs