All graphs with at most three nodes are diamond-free, so a(n) = 1 for n <= 3 and any graph is optimal.
For 4 <= n <= 9, the following are all optimal graphs, i.e., graphs that have n nodes and a(n) maximal diamond-free subgraphs:
n = 4: the diamond graph;
n = 5: the wheel graph;
n = 6: the complement of the H graph, the complement of P_3 + P_3 (the disjoint union of two paths of length 2), and the octahedral graph;
n = 7: the complement of P_3 + P_4;
n = 8: the complement of P_3 + C_5, and the complement of 2*P_4;
n = 9: the complement of P_4 + C_5.
|