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

DOI10.1016/J.ENDM.2015.07.049zbMATH Open1347.05126arXiv1510.01165OpenAlexW2570278360MaRDI QIDQ5890936FDOQ5890936

Authors: Marina Groshaus, Leandro Montero 

Publication date: 17 October 2016

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Abstract: A emph{biclique} is a maximal bipartite complete induced subgraph of $G$. 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 $G$ 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 $$,false-twin$$-free graphs and for the class of $$,false-twin$$-free graphs. Finally we discuss the problem for general graphs.

Full work available at URL: https://arxiv.org/abs/1510.01165

Recommendations

• Tight lower bounds on the number of bicliques in false-twin-free graphs
• Bicliques in graphs. I: Bounds on their number
• On Independent Sets and Bicliques in Graphs
• On independent sets and bicliques in graphs
• Bicliques and eigenvalues

zbMATH Keywords

lower boundsbicliquesfalse-twin-free graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)

Cites Work

• Title not available (Why is that?)
• On Independent Sets and Bicliques in Graphs
• Bicliques in graphs. I: Bounds on their number
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• On the iterated biclique operator

Cited In (2)

• Bicliques in graphs. I: Bounds on their number
• Tight lower bounds on the number of bicliques in false-twin-free graphs

This page was built for publication: Tight lower bounds on the number of bicliques in false-twin-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890936)