On edge-sets of bicliques in graphs
A biclique is a maximal induced complete bipartite subgraph of a graph. We investigate the intersection structure of edge-sets of bicliques in a graph. Specifically, we study the associated edge-biclique hypergraph whose hyperedges are precisely the edge-sets of all bicliques. We characterize graphs...
Guardado en:
Autores principales: | , , |
---|---|
Formato: | Artículo publishedVersion |
Lenguaje: | Inglés |
Publicado: |
2012
|
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2698_Groshaus |
Aporte de: |
id |
paperaa:paper_0166218X_v160_n18_p2698_Groshaus |
---|---|
record_format |
dspace |
spelling |
paperaa:paper_0166218X_v160_n18_p2698_Groshaus2023-06-12T16:46:55Z On edge-sets of bicliques in graphs Discrete Appl Math 2012;160(18):2698-2708 Groshaus, M. Hell, P. Stacho, J. 2-section Biclique Clique graph Conformal Helly Hypergraph Intersection graph 2-section Biclique Clique graphs Conformal Helly Hypergraph Intersection graph Combinatorial mathematics Mathematical techniques Polynomial approximation A biclique is a maximal induced complete bipartite subgraph of a graph. We investigate the intersection structure of edge-sets of bicliques in a graph. Specifically, we study the associated edge-biclique hypergraph whose hyperedges are precisely the edge-sets of all bicliques. We characterize graphs whose edge-biclique hypergraph is conformal (i.e., it is the clique hypergraph of its 2-section) by means of a single forbidden induced obstruction, the triangular prism. Using this result, we characterize graphs whose edge-biclique hypergraph is Helly and provide a polynomial time recognition algorithm. We further study a hereditary version of this property and show that it also admits polynomial time recognition, and, in fact, is characterized by a finite set of forbidden induced subgraphs. We conclude by describing some interesting properties of the 2-section graph of the edge-biclique hypergraph. © 2011 Elsevier B.V. All rights reserved. Fil:Groshaus, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2012 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2698_Groshaus |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
language |
Inglés |
orig_language_str_mv |
eng |
topic |
2-section Biclique Clique graph Conformal Helly Hypergraph Intersection graph 2-section Biclique Clique graphs Conformal Helly Hypergraph Intersection graph Combinatorial mathematics Mathematical techniques Polynomial approximation |
spellingShingle |
2-section Biclique Clique graph Conformal Helly Hypergraph Intersection graph 2-section Biclique Clique graphs Conformal Helly Hypergraph Intersection graph Combinatorial mathematics Mathematical techniques Polynomial approximation Groshaus, M. Hell, P. Stacho, J. On edge-sets of bicliques in graphs |
topic_facet |
2-section Biclique Clique graph Conformal Helly Hypergraph Intersection graph 2-section Biclique Clique graphs Conformal Helly Hypergraph Intersection graph Combinatorial mathematics Mathematical techniques Polynomial approximation |
description |
A biclique is a maximal induced complete bipartite subgraph of a graph. We investigate the intersection structure of edge-sets of bicliques in a graph. Specifically, we study the associated edge-biclique hypergraph whose hyperedges are precisely the edge-sets of all bicliques. We characterize graphs whose edge-biclique hypergraph is conformal (i.e., it is the clique hypergraph of its 2-section) by means of a single forbidden induced obstruction, the triangular prism. Using this result, we characterize graphs whose edge-biclique hypergraph is Helly and provide a polynomial time recognition algorithm. We further study a hereditary version of this property and show that it also admits polynomial time recognition, and, in fact, is characterized by a finite set of forbidden induced subgraphs. We conclude by describing some interesting properties of the 2-section graph of the edge-biclique hypergraph. © 2011 Elsevier B.V. All rights reserved. |
format |
Artículo Artículo publishedVersion |
author |
Groshaus, M. Hell, P. Stacho, J. |
author_facet |
Groshaus, M. Hell, P. Stacho, J. |
author_sort |
Groshaus, M. |
title |
On edge-sets of bicliques in graphs |
title_short |
On edge-sets of bicliques in graphs |
title_full |
On edge-sets of bicliques in graphs |
title_fullStr |
On edge-sets of bicliques in graphs |
title_full_unstemmed |
On edge-sets of bicliques in graphs |
title_sort |
on edge-sets of bicliques in graphs |
publishDate |
2012 |
url |
http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2698_Groshaus |
work_keys_str_mv |
AT groshausm onedgesetsofbicliquesingraphs AT hellp onedgesetsofbicliquesingraphs AT stachoj onedgesetsofbicliquesingraphs |
_version_ |
1769810230258958336 |