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).
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
KEYWORD
nonn,more
AUTHOR
Pontus von Brömssen, Mar 08 2022
STATUS
approved