Biclique graphs and biclique matrices

A biclique of a graph G is a maximal induced complete bipartite 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 characterization of biclique graphs. Finally, we show that every induced P 3 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. J Graph Theory 63: 1–16, 2010