Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #20 Mar 18 2022 00:14:21
%S 1,1,1,4,5,12,16,36,81
%N Largest number of maximal chordal node-induced subgraphs of an n-node graph.
%C 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). - _Pontus von Brömssen_, Mar 03 2022
%F a(m+n) >= a(m)*a(n).
%F Lim a(n)^(1/n) >= 3^(4/9).
%e All graphs with at most three nodes are chordal, so a(n) = 1 for n <= 3 and any graph will be optimal (containing 1 maximal chordal subgraph).
%e For 4 <= n <= 9, the following graphs are optimal:
%e n = 4: the 4-cycle;
%e n = 5: the 5-cycle and the complete bipartite graph K_{2,3};
%e n = 6: the 3-prism graph and the octahedral graph;
%e n = 7: the 3-prism graph with one edge (not in a triangle) subdivided by an additional node, and the complete tripartite graph K_{2,2,3};
%e n = 8: the gyrobifastigium graph;
%e n = 9: the Paley graph of order 9.
%Y Cf. A048192, A048193.
%Y For a list of related sequences, see cross-references in A342211.
%K nonn,more
%O 1,4
%A _Pontus von Brömssen_, Mar 08 2021