A366755 Number of 1-tough unlabeled graphs on n vertices.
1, 1, 1, 3, 8, 48, 387, 6240, 178176
Offset: 1
Examples
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).
Links
- Wikipedia, Graph toughness.
Formula
a(n) <= A002218(n) for n >= 2 because all 1-tough graphs (except the 1-node graph) are 2-connected.