Complete bipartite graph

This MedLibrary.org supplementary page on Complete bipartite graph is provided directly from the open source Wikipedia as a service to our readers. Please see the note below on authorship of this content, as well as the Wikipedia usage guidelines. To search for other content from our encyclopedia supplement, please use the form below:

Related Sponsors

BM Pharmacy Generic pharmaceuticals at unbeatable prices. Insomnia, men's health, hair health, pain control. bmpharmacy.com

Online Pharmacy Carisoprodol, tadalafil, sildenafil, vardenafil and more... xlpharmacy.com

MedBasket.com Discreet. Inexpensive. Fast shipping. Great selection. What more can we say? medbasket.com

Frugalmed 2000 reasons to shop with us first. frugalmed.com

Ads by Tiva

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 •

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

Welcome to the MedLibrary.org Wikipedia Supplement on Complete bipartite graph -- Please Click to Return to Front Page