cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A342324 Largest number of maximal chordal node-induced subgraphs of an n-node graph.

This page as a plain text file.
%I A342324 #20 Mar 18 2022 00:14:21
%S A342324 1,1,1,4,5,12,16,36,81
%N A342324 Largest number of maximal chordal node-induced subgraphs of an n-node graph.
%C A342324 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 A342324 a(m+n) >= a(m)*a(n).
%F A342324 Lim a(n)^(1/n) >= 3^(4/9).
%e A342324 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 A342324 For 4 <= n <= 9, the following graphs are optimal:
%e A342324   n = 4: the 4-cycle;
%e A342324   n = 5: the 5-cycle and the complete bipartite graph K_{2,3};
%e A342324   n = 6: the 3-prism graph and the octahedral graph;
%e A342324   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 A342324   n = 8: the gyrobifastigium graph;
%e A342324   n = 9: the Paley graph of order 9.
%Y A342324 Cf. A048192, A048193.
%Y A342324 For a list of related sequences, see cross-references in A342211.
%K A342324 nonn,more
%O A342324 1,4
%A A342324 _Pontus von Brömssen_, Mar 08 2021