Paper Info
Title
A convexity upper bound for the number of maximal bicliques of a bipartite graph.
Abstract
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.
Year
DOI
Venue
2014
10.1016/j.dam.2013.01.014
Discrete Applied Mathematics
Keywords
Field
DocType
convex property,bipartite graph,particular family,appropriate subgraphs,bipartite convexity,maximal bicliques,upper bound,known bound
Complete bipartite graph,Discrete mathematics,Graph,Combinatorics,Convexity,Polynomial,Upper and lower bounds,Bipartite graph,Convex bipartite graph,Regular polygon,Mathematics
Journal
Volume
ISSN
Citations 
165
0166-218X
6
PageRank 
References 
Authors
0.61
9
2
Name
Order
Citations
PageRank
Alexandre Albano181.46
Alair Pereira Do Lago210610.10