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

1, 1, 1, 4, 5, 12, 16, 36, 81

Offset

1,4

Comments

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

Links

Table of n, a(n) for n=1..9.

Formula

a(m+n) >= a(m)*a(n).

Lim a(n)^(1/n) >= 3^(4/9).

Example

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).
For 4 <= n <= 9, the following graphs are optimal:
  n = 4: the 4-cycle;
  n = 5: the 5-cycle and the complete bipartite graph K_{2,3};
  n = 6: the 3-prism graph and the octahedral graph;
  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};
  n = 8: the gyrobifastigium graph;
  n = 9: the Paley graph of order 9.

Crossrefs

Cf. A048192, A048193.

For a list of related sequences, see cross-references in A342211.

Sequence in context: A103650 A131116 A352215 * A261692 A131328 A054451

Adjacent sequences: A342321 A342322 A342323 * A342325 A342326 A342327

Keyword

nonn,more

Author

Pontus von Brömssen, Mar 08 2021

Status

approved