The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A342211 Largest number of maximal acyclic node-induced subgraphs of an n-node graph. 3
 1, 1, 3, 6, 10, 15, 22, 38, 64 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 LINKS Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon, On the minimum feedback vertex set problem: exact and enumeration algorithms, Algorithmica 52 (2008), 293-307. FORMULA a(m+n) >= a(m)*a(n). a(10) >= 105. 1.5926... = 105^(1/10) <= liminf a(n)^(1/n) <= limsup a(n)^(1/n) <= 1.8638. (Fomin, Gaspers, Pyatkin, and Razgon (2008)). EXAMPLE The following list shows all optimal graphs (i.e., graphs having n nodes and a(n) maximal acyclic subgraphs) for 1 <= n <= 9. Here, CK(n_1, ..., n_k) is the graph obtained by arranging complete graphs of orders n_1, ..., n_k (in that order) in a cycle, and joining all nodes in neighboring parts with edges. (The graph in the paper by Fomin, Gaspers, Pyatkin, and Razgon, which shows that a(10) >= 105, is CK(2, 2, 2, 2, 2).)         n = 1: the 1-node graph;         n = 2: the complete graph and the empty graph;   3 <= n <= 6: the complete graph;         n = 7: CK(1, 2, 2, 2);         n = 8: CK(1, 2, 1, 2, 2);         n = 9: CK(1, 2, 2, 1, 3). CROSSREFS Cf. A342212, A342213, A342324. Sequence in context: A137358 A143963 A139714 * A262927 A063542 A294413 Adjacent sequences:  A342208 A342209 A342210 * A342212 A342213 A342214 KEYWORD nonn,more AUTHOR Pontus von BrÃ¶mssen, Mar 05 2021 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 13 11:36 EDT 2021. Contains 344990 sequences. (Running on oeis4.)