The OEIS is supported by the many generous donors to the OEIS Foundation.
Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%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