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,5

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

Links

Table of n, a(n) for n=1..9.

Formula

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

Limit_{n->oo} a(n)^(1/n) >= 42^(1/9) = 1.51482... .

Example

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.

Sequence in context: A164927 A094904 A286456 * A171663 A126439 A318541

Adjacent sequences: A352206 A352207 A352208 * A352210 A352211 A352212

Keyword

nonn,more

Author

Pontus von Brömssen, Mar 08 2022

Status

approved