Tight lower bounds on the number of bicliques in false-twin-free graphs

preprint2016arXivOpen access

Abstract

A \emph{biclique} is a maximal bipartite complete induced subgraph of GG. Bicliques have been studied in the last years motivated by the large number of applications. In particular, enumeration of the maximal bicliques has been of interest in data analysis. Associated with this issue, bounds on the maximum number of bicliques were given. In this paper we study bounds on the minimun number of bicliques of a graph. Since adding false-twin vertices to GG does not change the number of bicliques, we restrict to false-twin-free graphs. We give a tight lower bound on the minimum number bicliques for a subclass of {C4\{C_4,false-twin}\}-free graphs and for the class of {K3\{K_3,false-twin}\}-free graphs. Finally we discuss the problem for general graphs.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.