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!)
 A342212 Largest number of maximal bipartite node-induced subgraphs of an n-node graph. 3
 1, 1, 3, 6, 10, 15, 21, 38, 64 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Byskov, Madsen, and Skjernaa (2005) construct a 10-node graph with 105 maximal bipartite subgraphs, so a(10) >= 105. By taking disjoint copies of this graph, it follows that a(10*n) >= 105^n. LINKS Jesper Makholm Byskov, Bolette Ammitzbøll Madsen, and Bjarke Skjernaa, On the number of maximal bipartite subgraphs of a graph, Journal of Graph Theory 48 (2005), 127-132. FORMULA a(m+n) >= a(m)*a(n). a(n) <= n*12^(n/4). (Byskov, Madsen, and Skjernaa (2005)) 1.5926... = 105^(1/10) <= liminf a(n)^(1/n) <= limsup a(n)^(1/n) <= 12^(1/4) = 1.8612... . (Byskov, Madsen, and Skjernaa (2005)) EXAMPLE The following list shows all optimal graphs (i.e., graphs having n nodes and a(n) maximal bipartite 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 Byskov, Madsen, and Skjernaa, 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, 1, 2, 1, 2) (the Moser spindle) and the complete graph;         n = 8: CK(1, 2, 1, 2, 2) and the 4-antiprism graph;         n = 9: CK(1, 2, 2, 1, 3). CROSSREFS Cf. A342211, A342213, A342324. Sequence in context: A188279 A174163 A152899 * A061304 A109442 A288425 Adjacent sequences:  A342209 A342210 A342211 * A342213 A342214 A342215 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 19 15:58 EDT 2021. Contains 345144 sequences. (Running on oeis4.)