cp's OEIS Frontend

A352211 Largest number of maximal node-induced cluster subgraphs of an n-node graph.

%I A352211 #9 Mar 15 2022 05:23:04
%S A352211 1,1,3,6,8,11,18,36,48
%N A352211 Largest number of maximal node-induced cluster subgraphs of an n-node graph.
%C A352211 This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).
%C A352211 Assuming that there exists a disconnected optimal graph for n >= 7 (this is the case for 7 <= n <= 9), it would hold that a(n) = 6*a(n-4) for n >= 7.
%F A352211 a(m+n) >= a(m)*a(n).
%F A352211 Limit_{n->oo} a(n)^(1/n) >= 6^(1/4) = 1.56508... .
%e A352211 For 3 <= n <= 9, the following are all optimal graphs, i.e., graphs that have n nodes and a(n) maximal cluster subgraphs:
%e A352211   n = 3: the path of length 2;
%e A352211   n = 4: the 4-cycle;
%e A352211   n = 5: K_{2,3};
%e A352211   n = 6: the Hajós graph (also known as a Sierpiński sieve graph), the square pyramid with an additional node with an edge to the top of the pyramid, K_{3,3}, the prism graph, and the octahedral graph;
%e A352211   n = 7: the disjoint union of any optimal graph for n = 3 and any optimal graph for n = 4;
%e A352211   n = 8: the disjoint union of any two optimal graphs for n = 4;
%e A352211   n = 9: the disjoint union of any optimal graph for n = 4 and any optimal graph for n = 5.
%Y A352211 Cf. A000041 (number of cluster graphs on n nodes).
%Y A352211 For a list of related sequences, see cross-references in A342211.
%K A352211 nonn,more
%O A352211 1,3
%A A352211 _Pontus von Brömssen_, Mar 08 2022