All graphs with at most three nodes are cographs, so a(n) = 1 for n <= 3 and any graph is optimal.
All optimal graphs (i.e., graphs that have n nodes and a(n) maximal cographical subgraphs) for 4 <= n <= 9 are listed below. Since a graph is a cograph if and only if its complement is a cograph, the optimal graphs come in complementary pairs.
n = 4: the path of length 3 (self-complementary);
n = 5: the 5-cycle (self-complementary);
n = 6: the Hajós graph (also known as a Sierpiński sieve graph) and its complement;
n = 7: the elongated triangular pyramid and its complement;
n = 8: the Möbius ladder and its complement (the antiprism graph);
n = 9: the pentagonal bipyramid with an additional path of length 3 between the two apex nodes (self-complementary).
|