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...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03649024_v63_n1_p1_Groshaus |
| Aporte de: |
| Sumario: | 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. |
|---|