A366755 - OEIS

%I #9 Feb 12 2024 15:17:47

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

%N Number of 1-tough unlabeled graphs on n vertices.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Graph_toughness">Graph toughness</a>.

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

%e 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).

%Y Cf. A002218, A007031, A366315, A366756.

%K nonn,more

%O 1,4

%A _Pontus von Brömssen_, Oct 20 2023