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) >= 118^(1/11) = 1.54295... . [Updated using a(11) by Martin Fuller, Jun 20 2026]
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.
From Martin Fuller, Jun 20 2026: (Start)
n = 10: graph6 format "I?otvHytO", "I?relpxN_", "ICZbeq]mO" and "ICdffP[NG";
n = 11: graph6 format "JCQb`rK}Cn?" and "JCZbeqxzbj?". (End)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Pontus von Brömssen, Mar 08 2022
EXTENSIONS
a(10)-a(11) from Martin Fuller, Jun 20 2026
STATUS
approved