cp's OEIS Frontend

A352213 Largest number of maximal cographical node-induced subgraphs of an n-node graph.

%I A352213 #8 Mar 15 2022 05:23:29
%S A352213 1,1,1,4,10,12,23,38,64
%N A352213 Largest number of maximal cographical node-induced subgraphs of an n-node graph.
%C A352213 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).
%F A352213 a(m+n) >= a(m)*a(n).
%F A352213 Limit_{n->oo} a(n)^(1/n) >= 64^(1/9) = 1.58740... .
%e A352213 All graphs with at most three nodes are cographs, so a(n) = 1 for n <= 3 and any graph is optimal.
%e A352213 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.
%e A352213   n = 4: the path of length 3 (self-complementary);
%e A352213   n = 5: the 5-cycle (self-complementary);
%e A352213   n = 6: the Hajós graph (also known as a Sierpiński sieve graph) and its complement;
%e A352213   n = 7: the elongated triangular pyramid and its complement;
%e A352213   n = 8: the Möbius ladder and its complement (the antiprism graph);
%e A352213   n = 9: the pentagonal bipyramid with an additional path of length 3 between the two apex nodes (self-complementary).
%Y A352213 Cf. A000084, A000669.
%Y A352213 For a list of related sequences, see cross-references in A342211.
%K A352213 nonn,more
%O A352213 1,4
%A A352213 _Pontus von Brömssen_, Mar 08 2022