Complete bipartite graph

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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!

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.

1 Definition
2 Examples
3 Properties
4 See also

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$ .

Examples

K_1,3

K_2,3

K_3,3

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 $m\cdot 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{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}$
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
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

Complete bipartite graph

Contents

Definition

Examples

Properties

See also