Science Fair Project Encyclopedia
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertices of the first set is connected to every vertex of the second set.
Similar to complete graphs they have very nice properties.
| Contents |
Definition
A complete bipartite graph G: = (V1 + V2,E) is a bipartite graph such that for any two vertices 
and 
v1v2 is an edge in G. A complete bipartite graph with partitions of size 
and 
is denoted Km,n.
Examples
Properties
- A planar graph cannot contain K3,3 as a minor.
- A complete bipartite graph Km,n has a vertex covering number of min{m,n} and an edge covering number of max{m,n}
- A complete bipartite graph Km,n has a maximum independent set of size max{m,n}
- A complete bipartite graph Km,n has a perfect matching of size min{m,n}
See also
09-23-2007 01:00:40
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details