Complete bipartite graph

Complete bipartite graph
A complete bipartite graph with m = 5 and n = 3
Vertices	n + m
Edges	mn
Radius	$\left\{\begin{array}{ll}1 & m = 1 \vee n = 1\\ 2 & \text{otherwise}\end{array}\right.$
Diameter	$\left\{\begin{array}{ll}1 & m = n = 1\\ 2 & \text{otherwise}\end{array}\right.$
Girth	$\left\{\begin{array}{ll}\infty & m = 1 \vee n = 1\\ 4 & \text{otherwise}\end{array}\right.$
Automorphisms	$\left\{\begin{array}{ll}2 m! n! & n = m\\ m! n! & \text{otherwise}\end{array}\right.$
Chromatic number	2
Chromatic index	max{m, n}
Spectrum	$\{0^{n + m - 2}, (\pm \sqrt{n m})^1\}$
Notation	Km,n

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₁ + V₂, E), is a bipartite graph such that for any two vertices, v₁ ∈ V₁ and v₂ ∈ V₂, v₁v₂ is an edge in G. The complete bipartite graph with partitions of size |V₁|=m and |V₂|=n, is denoted K_m,n.

Examples

The star graphs S₃, S₄, S₅ and S₆.

The utility graph K_3,3

• For any k, K_1,k is called a star. All complete bipartite graphs which are trees are stars.
• The graph K_1,3 is called a claw, and is used to define the claw-free graphs.
• The graph K_3,3 is called the utility graph. This usage comes from a standard mathematical puzzle in which three utilities must each be connected to three buildings; it is impossible to solve without crossings due to the nonplanarity of K_3,3.

Properties

• Given a bipartite graph, finding its complete bipartite subgraph K_m,n with maximal number of edges mn is an 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{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}.
• The adjacency matrix of a complete bipartite graph K_m,n has eigenvalues √(nm), −√(nm) and 0; with multiplicity 1, 1 and n+m−2 respectively.
• The laplacian matrix of a complete bipartite graph K_m,n has eigenvalues n+m, n, m, and 0; with multiplicity 1, m−1, n−1 and 1 respectively.
• A complete bipartite graph K_m,n has mⁿ⁻¹ n^m−1 spanning trees.
• 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 corresponding to a Latin square.
• The last two results are corollaries of the Marriage Theorem as applied to a k-regular bipartite graph.

See also

• Cycle graph
• Path graph
• Crown graph
• Complete graph
• Null graph
• Adjacency matrix

References

• Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7, http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html , page 5.
• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6 . Electronic edition, page 17.