The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A352208 Largest number of maximal 3-colorable node-induced subgraphs of an n-node graph. 1
1, 1, 1, 4, 10, 20, 35, 56, 84 (list; graph; refs; listen; history; text; internal format)
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).
In the following, 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.
a(10) >= 140 by FCB(2, 2, 2, 2, 2);
a(11) >= 268 by FCB(2, 2, 2, 2, 3);
a(12) >= 517 by FCB(2, 2, 3, 2, 3);
a(13) >= 911 by FCB(2, 3, 2, 3, 3);
a(14) >= 1515 by FCB(2, 3, 3, 3, 3);
a(15) >= 2525 by FCB(3, 3, 3, 3, 3).
LINKS
Natasha Morrison and Alex Scott, Maximising the number of induced cycles in a graph, Journal of Combinatorial Theory Series B 126 (2017), 24-61.
FORMULA
a(m+n) >= a(m)*a(n).
Limit_{n->oo} a(n)^(1/n) >= 911^(1/13) = 1.68909... .
EXAMPLE
For 3 <= n <= 9, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is optimal (it is the unique optimal graph for 4 <= n <= 9), but a(10) >= 140 > binomial(10,3).
CROSSREFS
For a list of related sequences, see cross-references in A342211.
Sequence in context: A038409 A347252 A201722 * A341193 A090579 A276643
KEYWORD
nonn,more
AUTHOR
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 17 19:53 EDT 2024. Contains 372607 sequences. (Running on oeis4.)