A366755 Number of 1-tough unlabeled graphs on n vertices.

1, 1, 1, 3, 8, 48, 387, 6240, 178176

Offset

1,4

Links

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

Wikipedia, Graph toughness.

Formula

a(n) <= A002218(n) for n >= 2 because all 1-tough graphs (except the 1-node graph) are 2-connected.

Example

For n = 5, all but two of the A002218(5) = 10 2-connected graphs are 1-tough, so a(5) = 8. The exceptions are the complete bipartite graph K_{2,3} and the complete tripartite graph K_{1,1,3}. To see that these graphs are not 1-tough, note that, in both cases, two vertices can be removed resulting in a graph with three components (isolated vertices).

Crossrefs

Cf. A002218, A007031, A366315, A366756.

Sequence in context: A291504 A034183 A003216 * A146161 A304698 A306598

Adjacent sequences: A366752 A366753 A366754 * A366756 A366757 A366758

Keyword

nonn,more

Author

Pontus von Brömssen, Oct 20 2023

Status

approved