cp's OEIS Frontend

A352215 Largest number of maximal C_4-free node-induced subgraphs of an n-node graph.

%I A352215 #11 Mar 24 2022 08:37:11
%S A352215 1,1,1,4,5,12,16,32,54
%N A352215 Largest number of maximal C_4-free node-induced subgraphs of an n-node graph.
%C A352215 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 A352215 a(m+n) >= a(m)*a(n).
%F A352215 Limit_{n->oo} a(n)^(1/n) >= 54^(1/9) = 1.55771... .
%e A352215 All graphs with at most three nodes are C_4-free, so a(n) = 1 for n <= 3 and any graph is optimal.
%e A352215 For 4 <= n <= 9, the following are all optimal graphs, i.e., graphs that have n nodes and a(n) maximal C_4-free subgraphs:
%e A352215   n = 4: the 4-cycle;
%e A352215   n = 5: K_{2,3};
%e A352215   n = 6: the prism graph and the octahedral graph;
%e A352215   n = 7: the complement of 2*K_2 + K_3;
%e A352215   n = 8: K_4 X K_2 (Cartesian product) and the 16-cell;
%e A352215   n = 9: the circulant graph C_9(1,3), and K_{3,3,3} with three edges removed, one edge between the first and second parts in the partition and two edges from two other nodes in these two parts to a node in the third part.
%Y A352215 Cf. A079566, A352068.
%Y A352215 For a list of related sequences, see cross-references in A342211.
%K A352215 nonn,more
%O A352215 1,4
%A A352215 _Pontus von Brömssen_, Mar 08 2022