A366756 - OEIS

%I #6 Oct 21 2023 06:16:52

%S 1,1,1,1,1,1,2,2,5

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

%C A graph is minimally 1-tough if it is 1-tough but the removal of any of its edges makes it non-1-tough.

%H House of Graphs, <a href="https://houseofgraphs.org/graphs/536">Graph 536</a>.

%H House of Graphs, <a href="https://houseofgraphs.org/graphs/36063">Graph 36063</a>.

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

%e For n >= 3, the cycle graph is minimally 1-tough. For 3 <= n <= 6, this is the only minimally 1-tough graph, so a(n) = 1.

%e For n = 7 and n = 8, the graphs with House of Graphs id's 536 and 36063, respectively, are also minimally 1-tough, and a(7) = a(8) = 2.

%e For n = 9, the a(9) = 5 minimally 1-tough graphs are (in graph6 format) "H?CidB?" (9-cycle), "H?Cicr_", "H?Ci[b_", "H?Ci[^o", and "H?KqKVO".

%Y Cf. A003317, A366755.

%K nonn,more

%O 1,7

%A _Pontus von Brömssen_, Oct 20 2023