Complete bipartite graph
Encyclopedia : C : CO : COM : 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 vertex of the first set is connected to every vertex of the second set.
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_].Examples
Properties
- A planar graph cannot contain [K_] as a minor; an outerplanar graph cannot contain [K_] as a minor. (These are not sufficient conditions for planarity and outerplanarity, but necessary.)
- A complete bipartite graph [K_] has a vertex covering number of [\min \lbrace m,n \rbrace] and an edge covering number of [\max\lbrace m,n\rbrace]
- A complete bipartite graph [K_] has a maximum independent set of size [\max\lbrace m,n\rbrace]
- A complete bipartite graph [K_] has a perfect matching of size [\min\lbrace m,n\rbrace]
- A complete bipartite graph [K_] 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
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.