Complete bipartite graph

From Wikipedia, the free encyclopedia

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

1 Definition
2 Examples
3 Properties
4 See also

[edit] Definition

A complete bipartite graph $G : = (V 1 + V 2, E)$ is a bipartite graph such that for any two vertices $v_1 \in V_1$ and $v_2 \in V_2$ $v 1 v 2$ is an edge in $G$ . The complete bipartite graph with partitions of size $\left|V_1\right|=m$ and $\left|V_2\right|=n,$ is denoted $K m, n$ .

[edit] Examples

K_1,3

K_2,3

K_3,3

[edit] Properties

Given a bipartite graph, finding its complete bipartite subgraph $K m, n$ with maximal number of edges $m\cdot n$ is a NP-complete problem.
A planar graph cannot contain $K 3,3$ as a minor; an outerplanar graph cannot contain $K 3,2$ as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary).
A complete bipartite graph $K n, n$ is a Moore graph and a cage
A complete bipartite graph $K n, n$ or $K n, n + 1$ is a Turán graph
A complete bipartite graph $K m, n$ has a vertex covering number of $min{m, n}$ and an edge covering number of $max{m, n}$
A complete bipartite graph $K m, n$ has a maximum independent set of size $max{m, n}$
A complete bipartite graph $K m, n$ has a maximum matching of size $min{m, n}$
A complete bipartite graph $K n, n$ has a proper n-edge-coloring
The last two results are corollaries of the Marriage Theorem as applied to a k-regular bipartite graph