A352209 Largest number of maximal perfect node-induced subgraphs of an n-node graph.

1, 1, 1, 1, 5, 5, 13, 18, 42

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).

Examples

			All graphs with at most four nodes are perfect, so a(n) = 1 for n <= 4 and any graph is optimal.
All optimal graphs (i.e., graphs that have n nodes and a(n) maximal perfect subgraphs) for 5 <= n <= 9 are listed below. Since a graph is perfect if and only if its complement is perfect, the optimal graphs come in complementary pairs.
  n = 5: the 5-cycle;
  n = 6: the wheel graph with any subset of the spokes removed (8 graphs in total);
  n = 7: the chestahedral graph and its complement;
  n = 8: the bislit cube graph, the snub disphenoidal graph, and their complements;
  n = 9: the bislit cube graph with an additional node with edges to two neighboring nodes of degree 4 and to the two nodes of degree 3 on the opposite face of the cube, the snub disphenoidal graph with an additional node with edges to the four nodes of degree 4, and their complements.
		

Crossrefs

Cf. A052431, A052433.

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) >= 42^(1/9) = 1.51482... .