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, bounds on the maximum...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2016
Materias:
Bicliques
False-twin-free graphs
Lower bounds
Computational methods
Computer science
Biclique
Free graphs
General graph
Induced subgraphs
Twin-free
Graphic methods
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v636_n_p77_Groshaus
http://hdl.handle.net/20.500.12110/paper_03043975_v636_n_p77_Groshaus
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03043975_v636_n_p77_Groshaus
record_format dspace
spelling paper:paper_03043975_v636_n_p77_Groshaus2023-06-08T15:29:40Z Tight lower bounds on the number of bicliques in false-twin-free graphs Bicliques False-twin-free graphs Lower bounds Computational methods Computer science Biclique Bicliques Free graphs General graph Induced subgraphs Lower bounds Twin-free Graphic methods 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, 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 {C4,false-twin}-free graphs and for the class of {K3,false-twin}-free graphs. Finally we discuss the problem for general graphs. © 2016 Elsevier B.V. 2016 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v636_n_p77_Groshaus http://hdl.handle.net/20.500.12110/paper_03043975_v636_n_p77_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
Computational methods
Computer science
Biclique
Bicliques
Free graphs
General graph
Induced subgraphs
Lower bounds
Twin-free
Graphic methods
spellingShingle Bicliques
False-twin-free graphs
Lower bounds
Computational methods
Computer science
Biclique
Bicliques
Free graphs
General graph
Induced subgraphs
Lower bounds
Twin-free
Graphic methods
Tight lower bounds on the number of bicliques in false-twin-free graphs
topic_facet Bicliques
False-twin-free graphs
Lower bounds
Computational methods
Computer science
Biclique
Bicliques
Free graphs
General graph
Induced subgraphs
Lower bounds
Twin-free
Graphic methods
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, 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 {C4,false-twin}-free graphs and for the class of {K3,false-twin}-free graphs. Finally we discuss the problem for general graphs. © 2016 Elsevier B.V.
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
publishDate 2016
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v636_n_p77_Groshaus
http://hdl.handle.net/20.500.12110/paper_03043975_v636_n_p77_Groshaus
_version_ 1768542081587871744

Ejemplares similares