Related Searches
Definitions

Complete bipartite graph

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.

Definition

A complete bipartite graph $G:=\left(V_1 + V_2, E\right)$ 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_1right|=m$ and $left|V_2right|=n,$ is denoted $K_\left\{m,n\right\}$.

Examples

• For any k, $K_\left\{1,k\right\}$ is called a star.
• The graph $K_\left\{1,3\right\}$ is called a claw.

Properties

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