Tight lower bounds on the number of bicliques in false-twin-free graphs
A 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, upper and lower bounds...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p293_Groshaus |
| Aporte de: |
| id |
todo:paper_15710653_v50_n_p293_Groshaus |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_15710653_v50_n_p293_Groshaus2023-10-03T16:27:09Z Tight lower bounds on the number of bicliques in false-twin-free graphs Groshaus, M. Montero, L. Bicliques False-twin-free graphs Lower bounds A 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, upper and lower bounds on the maximun number of bicliques were given. In this paper we study lower bounds on the 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 in {C4,diamond,false-twin}-free graphs, (K3,false-twin)-free graphs and we present some conjectures for general false-twin-free graphs. © 2015 Elsevier B.V. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p293_Groshaus |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Bicliques False-twin-free graphs Lower bounds |
| spellingShingle |
Bicliques False-twin-free graphs Lower bounds Groshaus, M. Montero, L. Tight lower bounds on the number of bicliques in false-twin-free graphs |
| topic_facet |
Bicliques False-twin-free graphs Lower bounds |
| description |
A 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, upper and lower bounds on the maximun number of bicliques were given. In this paper we study lower bounds on the 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 in {C4,diamond,false-twin}-free graphs, (K3,false-twin)-free graphs and we present some conjectures for general false-twin-free graphs. © 2015 Elsevier B.V. |
| format |
JOUR |
| author |
Groshaus, M. Montero, L. |
| author_facet |
Groshaus, M. Montero, L. |
| author_sort |
Groshaus, M. |
| title |
Tight lower bounds on the number of bicliques in false-twin-free graphs |
| title_short |
Tight lower bounds on the number of bicliques in false-twin-free graphs |
| title_full |
Tight lower bounds on the number of bicliques in false-twin-free graphs |
| title_fullStr |
Tight lower bounds on the number of bicliques in false-twin-free graphs |
| title_full_unstemmed |
Tight lower bounds on the number of bicliques in false-twin-free graphs |
| title_sort |
tight lower bounds on the number of bicliques in false-twin-free graphs |
| url |
http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p293_Groshaus |
| work_keys_str_mv |
AT groshausm tightlowerboundsonthenumberofbicliquesinfalsetwinfreegraphs AT monterol tightlowerboundsonthenumberofbicliquesinfalsetwinfreegraphs |
| _version_ |
1782030582204596224 |