
COMMENTS

Byskov, Madsen, and Skjernaa (2005) construct a 10node 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.


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 1node 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 4antiprism graph;
n = 9: CK(1, 2, 2, 1, 3).
