login
Largest number of maximal bipartite node-induced subgraphs of an n-node graph.
1

%I #23 Mar 18 2022 00:14:00

%S 1,1,3,6,10,15,21,38,64

%N Largest number of maximal bipartite node-induced subgraphs of an n-node graph.

%C 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). - _Pontus von Brömssen_, Mar 03 2022

%C Byskov, Madsen, and Skjernaa (2005) construct a 10-node graph with 105 maximal bipartite subgraphs, so a(10) >= 105.

%H Jesper Makholm Byskov, Bolette Ammitzbøll Madsen, and Bjarke Skjernaa, <a href="https://doi.org/10.1002/jgt.20041">On the number of maximal bipartite subgraphs of a graph</a>, Journal of Graph Theory 48 (2005), 127-132.

%H Natasha Morrison and Alex Scott, <a href="http://dx.doi.org/10.1016/j.jctb.2017.03.007">Maximising the number of induced cycles in a graph</a>, Journal of Combinatorial Theory Series B 126 (2017), 24-61.

%F a(m+n) >= a(m)*a(n).

%F a(n) <= n*12^(n/4). (Byskov, Madsen, and Skjernaa (2005))

%F 1.5926... = 105^(1/10) <= lim_{n->oo} a(n)^(1/n) <= 12^(1/4) = 1.8612... . (Byskov, Madsen, and Skjernaa (2005))

%e All optimal graphs (i.e., graphs having n nodes and a(n) maximal bipartite subgraphs) for 1 <= n <= 9 are listed below. Here, 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. (The graph in the paper by Byskov, Madsen, and Skjernaa, which shows that a(10) >= 105, is FCB(2, 2, 2, 2, 2).)

%e n = 1: the 1-node graph;

%e n = 2: the complete graph and the empty graph;

%e 3 <= n <= 6: the complete graph;

%e n = 7: FCB(1, 1, 2, 1, 2) (the Moser spindle) and the complete graph;

%e n = 8: FCB(1, 2, 1, 2, 2) and the 4-antiprism graph;

%e n = 9: FCB(1, 2, 2, 1, 3).

%Y Cf. A005142, A033995.

%Y For a list of related sequences, see cross-references in A342211.

%K nonn,more

%O 1,3

%A _Pontus von Brömssen_, Mar 05 2021