On edge-sets of bicliques in graphs

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Groshaus, M., Hell, P., Stacho, J.
Formato:	Artículo publishedVersion
Publicado:	2012
Materias:	2-section Biclique Clique graph Conformal Helly Hypergraph Intersection graph Clique graphs Combinatorial mathematics Mathematical techniques Polynomial approximation
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2698_Groshaus https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v160_n18_p2698_Groshaus_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-paper_0166218X_v160_n18_p2698_Groshaus_oai
record_format	dspace
spelling	I28-R145-paper_0166218X_v160_n18_p2698_Groshaus_oai2024-08-16 Groshaus, M. Hell, P. Stacho, J. 2012 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. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2698_Groshaus info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2012;160(18):2698-2708 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 On edge-sets of bicliques in graphs info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v160_n18_p2698_Groshaus_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
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 https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v160_n18_p2698_Groshaus_oai
work_keys_str_mv	AT groshausm onedgesetsofbicliquesingraphs AT hellp onedgesetsofbicliquesingraphs AT stachoj onedgesetsofbicliquesingraphs
_version_	1809356902125010944

On edge-sets of bicliques in graphs

Ejemplares similares