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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Groshaus, Marina E.
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:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v160_n18_p2698_Groshaus
http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2698_Groshaus
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_0166218X_v160_n18_p2698_Groshaus
record_format dspace
spelling paper:paper_0166218X_v160_n18_p2698_Groshaus2023-06-08T15:15:31Z On edge-sets of bicliques in graphs Groshaus, Marina E. 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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v160_n18_p2698_Groshaus 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)
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, Marina E.
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.
author Groshaus, Marina E.
author_facet Groshaus, Marina E.
author_sort Groshaus, Marina E.
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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v160_n18_p2698_Groshaus
http://hdl.handle.net/20.500.12110/paper_0166218X_v160_n18_p2698_Groshaus
work_keys_str_mv AT groshausmarinae onedgesetsofbicliquesingraphs
_version_ 1768546295757144064

Ejemplares similares