A convexity upper bound for the number of maximal bicliques of a bipartite graph

作者：Albano Alexandre^*; do Lago Alair Pereira

来源：Discrete Applied Mathematics, 2014, 165: 12-24.

DOI：10.1016/j.dam.2013.01.014

• Maximal bicliques
• Convex bipartite graph
• Consecutive ones property

Given a bipartite graph, we present an upper bound for its number of maximal bicliques as the product of the numbers of maximal bicliques of two appropriate subgraphs. Such an upper bound is a function of bipartite convexity, a generalization of the convex property for bipartite graphs. We survey known upper bounds present in the literature and construct families of graphs for which our bound is sharper than all the other known bounds. For particular families, only our upper bound is polynomial. We also show that determining convexity is NP-hard.

• 出版日期2014-3-11