Biclique graphs and biclique matrices

A biclique of a graph G is a maximal induced complete bipar tite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1, -1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, -1 entries in a same row corresponds exactly to adjacent ve...

Descripción completa

Guardado en:

Detalles Bibliográficos
Publicado:	2010
Materias:	Biclique graphs Bicliques Bipartite matrices Clique graphs Cliques Adjacent vertices Biclique Bipartite graphs Graph G Intersection graph matrix Subgraphs
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v63_n1_p1_Groshaus http://hdl.handle.net/20.500.12110/paper_03649024_v63_n1_p1_Groshaus
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03649024_v63_n1_p1_Groshaus
record_format	dspace
spelling	paper:paper_03649024_v63_n1_p1_Groshaus2023-06-08T15:35:37Z Biclique graphs and biclique matrices Biclique graphs Bicliques Bipartite matrices Clique graphs Cliques Adjacent vertices Biclique Bipartite graphs Clique graphs Graph G Intersection graph matrix Subgraphs A biclique of a graph G is a maximal induced complete bipar tite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1, -1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, -1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz-type char acterization of biclique graphs. Finally, we show that every induced P3 of a biclique graph must be included in a diamond or in a 3-fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, inc. 2010 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v63_n1_p1_Groshaus http://hdl.handle.net/20.500.12110/paper_03649024_v63_n1_p1_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	Biclique graphs Bicliques Bipartite matrices Clique graphs Cliques Adjacent vertices Biclique Bipartite graphs Clique graphs Graph G Intersection graph matrix Subgraphs
spellingShingle	Biclique graphs Bicliques Bipartite matrices Clique graphs Cliques Adjacent vertices Biclique Bipartite graphs Clique graphs Graph G Intersection graph matrix Subgraphs Biclique graphs and biclique matrices
topic_facet	Biclique graphs Bicliques Bipartite matrices Clique graphs Cliques Adjacent vertices Biclique Bipartite graphs Clique graphs Graph G Intersection graph matrix Subgraphs
description	A biclique of a graph G is a maximal induced complete bipar tite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1, -1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, -1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz-type char acterization of biclique graphs. Finally, we show that every induced P3 of a biclique graph must be included in a diamond or in a 3-fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, inc.
title	Biclique graphs and biclique matrices
title_short	Biclique graphs and biclique matrices
title_full	Biclique graphs and biclique matrices
title_fullStr	Biclique graphs and biclique matrices
title_full_unstemmed	Biclique graphs and biclique matrices
title_sort	biclique graphs and biclique matrices
publishDate	2010
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v63_n1_p1_Groshaus http://hdl.handle.net/20.500.12110/paper_03649024_v63_n1_p1_Groshaus
_version_	1768542888569864192

Biclique graphs and biclique matrices

Ejemplares similares