Complete bipartite graph

	Complete bipartite graph
	; A complete bipartite graph m=3 n =2
Vertices	n+m
Edges	mn
Automorphisms	2m!n! if m=n, otherwise m!n!
	This box: view • talk

From Wikipedia, the free encyclopedia

Jump to: navigation, search

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.

[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

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.
The graph $K 3,3$ is called the utility graph.

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

K_1,1	K_2,1	K_2,2	K_3,1
K_3,2	K_3,3	K_7,1

[edit] Properties

Given a bipartite graph, finding its complete bipartite subgraph $K m, n$ with maximal number of edges $m\cdot n$ 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 $\sqrt{nm}$ , $-\sqrt{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-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