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 <math>G:=(V_1 + V_2, E)<math> is a bipartite graph such that for any two vertices <math>v_1 \in V_1<math> and <math>v_2 \in V_2<math> <math>v_1 v_2<math> is an edge in <math>G<math>. A complete bipartite graph with partitions of size <math>\|V_1\|=m<math> and <math>\|V_2\|=n<math> is denoted <math>K_{m,n}<math>.
Examples
Missing image
Complete_bipartite_graph_K3,1.png
Complete_bipartite_graph_K3,1.png
K3,1
Missing image
Complete_bipartite_graph_K3,2.png
Complete_bipartite_graph_K3,2.png
K3,2
Missing image
Complete_bipartite_graph_K3,3.png
Complete_bipartite_graph_K3,3.png
K3,3
Properties
- A planar graph cannot contain <math>K_{3,3}<math> as a minor; an outerplanar graph cannot contain <math>K_{2,3}<math> as a minor. (These are not sufficient conditions for planarity and outerplanarity, but necessary.)
- A complete bipartite graph <math>K_{m,n}<math> has a vertex covering number of <math>\min \lbrace m,n \rbrace<math> and an edge covering number of <math>\max\lbrace m,n\rbrace<math>
- A complete bipartite graph <math>K_{m,n}<math> has a maximum independent set of size <math>\max\lbrace m,n\rbrace<math>
- A complete bipartite graph <math>K_{m,n}<math> has a perfect matching of size <math>\min\lbrace m,n\rbrace<math>
- A complete bipartite graph <math>K_{n,n}<math> has a proper n-edge-coloring
- The last two results are corollaries of the Marriage Theorem as applied to a k-regular bipartite graph