Complete bipartite graph

Complete bipartite graph
A complete bipartite graph with m = 3 n = 2
Vertices	n + m
Edges	mn
Girth	4
Automorphisms	2m!n! if m=n, otherwise m!n!
Chromatic number	2
Chromatic index	max{m, n}
Notation	Km,n
This box: view • talk

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 and v₁v₂ is an edge in G. The complete bipartite graph with partitions of size and 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 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 , 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-1 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; Murthy, 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.