login
A352211
Largest number of maximal node-induced cluster subgraphs of an n-node graph.
1
1, 1, 3, 6, 8, 11, 18, 36, 48
OFFSET
1,3
COMMENTS
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).
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.
FORMULA
a(m+n) >= a(m)*a(n).
Limit_{n->oo} a(n)^(1/n) >= 6^(1/4) = 1.56508... .
EXAMPLE
For 3 <= n <= 9, the following are all optimal graphs, i.e., graphs that have n nodes and a(n) maximal cluster subgraphs:
n = 3: the path of length 2;
n = 4: the 4-cycle;
n = 5: K_{2,3};
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;
n = 7: the disjoint union of any optimal graph for n = 3 and any optimal graph for n = 4;
n = 8: the disjoint union of any two optimal graphs for n = 4;
n = 9: the disjoint union of any optimal graph for n = 4 and any optimal graph for n = 5.
CROSSREFS
Cf. A000041 (number of cluster graphs on n nodes).
For a list of related sequences, see cross-references in A342211.
Sequence in context: A289241 A234307 A175769 * A160277 A080598 A233541
KEYWORD
nonn,more
AUTHOR
STATUS
approved