Premium
Biclique graphs and biclique matrices
Author(s) -
Groshaus Marina,
Szwarcfiter Jayme L.
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20442
Subject(s) - complete bipartite graph , combinatorics , bipartite graph , mathematics , vertex (graph theory) , discrete mathematics , graph
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