Complete_bipartite_graph

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:=(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_1right|=m

and

left|V_2right|=n,

is denoted

K_{m,n}

Examples

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

Properties

Given a bipartite graph, finding its complete bipartite subgraph $K_{m,n}$ with maximal number of edges $mcdot 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 $(n,4)$ -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 lbrace m,n rbrace$ and an edge covering number of $maxlbrace m,nrbrace$
A complete bipartite graph $K_{m,n}$ has a maximum independent set of size $maxlbrace m,nrbrace$
A complete bipartite graph $K_{m,n}$ has a maximum matching of size $minlbrace m,nrbrace$
A complete bipartite graph $K_{n,n}$ has a proper n-edge-coloring
A complete bipartite graph $K_{m,n}$ has m^n-1 n^m-1 Spanning trees.
The last two results are corollaries of the Marriage Theorem as applied to a k-regular bipartite graph