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