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!)
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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 15:58 EDT 2021. Contains 345144 sequences. (Running on oeis4.)