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

 

Logo


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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

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