TOPICS
Search

Biclique


A biclique in a graph G is a complete bipartite graph that occurs as a subgraph of G. Thus, its vertex set can be partitioned into two parts so that every graph vertex in either part is adjacent to every graph vertex in the other part. Graph edges of G within either part are ignored when the biclique is not required to be an induced subgraph.

Usage varies: some authors require a biclique to be an induced subgraph that is a complete bipartite graph, while others use "biclique" for any complete bipartite graph occurring as a subgraph and state inducedness separately. A maximal biclique is one not properly contained in another biclique of G under the convention being used. This differs from an abstract complete bipartite graph, which need not be specified as a subgraph of a larger host graph.


See also

Biclique Cover, Bipartite Graph, Complete Bipartite Graph, Induced Subgraph

Explore with Wolfram|Alpha

References

Groshaus, M. and Szwarcfiter, J. L. "Biclique Graphs and Biclique Matrices." J. Graph Th. 63, 1-16, 2010. https://doi.org/10.1002/jgt.20442.

Cite this as:

Weisstein, Eric W. "Biclique." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Biclique.html

Subject classifications