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
Autores principales: Groshaus, M., Szwarcfiter, J.L.
Formato: JOUR
Materias:
Biclique graphs
Bicliques
Bipartite matrices
Clique graphs
Cliques
Adjacent vertices
Biclique
Bipartite graphs
Graph G
Intersection graph
matrix
Subgraphs
Acceso en línea: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 todo:paper_03649024_v63_n1_p1_Groshaus
record_format dspace
spelling todo:paper_03649024_v63_n1_p1_Groshaus2023-10-03T15:27:40Z Biclique graphs and biclique matrices Groshaus, M. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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
Groshaus, M.
Szwarcfiter, J.L.
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.
format JOUR
author Groshaus, M.
Szwarcfiter, J.L.
author_facet Groshaus, M.
Szwarcfiter, J.L.
author_sort Groshaus, M.
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
url http://hdl.handle.net/20.500.12110/paper_03649024_v63_n1_p1_Groshaus
work_keys_str_mv AT groshausm bicliquegraphsandbicliquematrices
AT szwarcfiterjl bicliquegraphsandbicliquematrices
_version_ 1807320001219133440

Ejemplares similares