|
%I #29 Mar 15 2022 05:22:10
%S 1,1,3,6,10,15,22,38,64
%N Largest number of maximal acyclic 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
%C a(10) >= 105.
%H Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon, <a href="https://doi.org/10.1007/s00453-007-9152-0">On the minimum feedback vertex set problem: exact and enumeration algorithms</a>, Algorithmica 52 (2008), 293-307.
%H Natasha Morrison and Alex Scott, <a href="http://dx.doi.org/10.1016/j.jctb.2017.03.007">Maximising the number of induced cycles in a graph</a>, Journal of Combinatorial Theory Series B 126 (2017), 24-61.
%F a(m+n) >= a(m)*a(n).
%F 1.5926... = 105^(1/10) <= lim_{n->oo} a(n)^(1/n) <= 1.8638. (Fomin, Gaspers, Pyatkin, and Razgon (2008)).
%e All optimal graphs (i.e., graphs having n nodes and a(n) maximal acyclic subgraphs) for 1 <= n <= 9 are listed below. Here, FCB(n_1, ..., n_k) denotes the full cyclic braid graph with cluster sizes n_1, ..., n_k, as defined by Morrison and Scott (2017), i.e., the graph obtained by arranging complete graphs of orders n_1, ..., n_k (in that order) in a cycle, and joining all pairs of nodes in neighboring parts with edges. (The graph in the paper by Fomin, Gaspers, Pyatkin, and Razgon, which shows that a(10) >= 105, is FCB(2, 2, 2, 2, 2).)
%e n = 1: the 1-node graph;
%e n = 2: the complete graph and the empty graph;
%e 3 <= n <= 6: the complete graph;
%e n = 7: FCB(1, 2, 2, 2);
%e n = 8: FCB(1, 2, 1, 2, 2);
%e n = 9: FCB(1, 2, 2, 1, 3).
%Y Cf. A000055, A005195.
%Y Sequences of largest number of maximal induced subgraphs with a given property:
%Y A000792 (independent sets or cliques),
%Y this sequence (acyclic),
%Y A342212 (bipartite),
%Y A342213 (planar),
%Y A342324 (chordal),
%Y A352208 (3-colorable),
%Y A352209 (perfect),
%Y A352210 (2-degenerate),
%Y A352211 (cluster graphs),
%Y A352212 (triangle-free),
%Y A352213 (cographs),
%Y A352214 (claw-free),
%Y A352215 (C_4-free),
%Y A352216 (diamond-free).
%K nonn,more
%O 1,3
%A _Pontus von Brömssen_, Mar 05 2021.
|
