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

1, 1, 3, 6, 8, 11, 18, 36, 48

Offset: 1

Author

Pontus von Brömssen, Mar 08 2022

Keywords

• nonn
• more

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.

Examples

			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.

Formula

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 6^(1/4) = 1.56508... .