Complete bipartite graph

From Free net encyclopedia

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.

Similar to complete graphs they have very nice properties.

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

K3,1

K3,2

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

See also

• bipartite graphth:กราฟสองส่วนบริบูรณ์

vi:Đồ thị hai phía đầy đủ