 Complete bipartite graph

Complete bipartite graph
A complete bipartite graph with m = 5 and n = 3Vertices n + m Edges mn Girth 4 Automorphisms 2m!n! if m=n, otherwise m!n! Chromatic number 2 Chromatic index max{m, n} Notation K_{m,n} v · 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. Contents
Definition
A complete bipartite graph, G := (V_{1} + V_{2}, E), is a bipartite graph such that for any two vertices, v_{1} ∈ V_{1} and v_{2} ∈ V_{2}, v_{1}v_{2} is an edge in G. The complete bipartite graph with partitions of size V_{1}=m and V_{2}=n, is denoted K_{m,n}.
Examples
 For any k, K_{1,k} is called a star. All complete bipartite graphs which are trees are stars.
 The graph K_{1,3} is called a claw, and is used to define the clawfree graphs.
 The graph K_{3,3} is called the utility graph. This usage comes from a standard mathematical puzzle in which three utilities must each be connected to three buildings; it is impossible to solve without crossings due to the nonplanarity of K_{3,3}.
Properties
 Given a bipartite graph, finding its complete bipartite subgraph K_{m,n} with maximal number of edges mn is an NPcomplete 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}.
 The adjacency matrix of a complete bipartite graph K_{m,n} has eigenvalues √(nm), −√(nm) and 0; with multiplicity 1, 1 and n+m−2 respectively.
 The laplacian matrix of a complete bipartite graph K_{m,n} has eigenvalues n+m, n, m, and 0; with multiplicity 1, m−1, n−1 and 1 respectively.
 A complete bipartite graph K_{m,n} has m^{n−1} n^{m−1} spanning trees.
 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 nedgecoloring corresponding to a Latin square.
 The last two results are corollaries of the Marriage Theorem as applied to a kregular bipartite graph.
See also
References
 Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, NorthHolland, ISBN 0444194517, http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html , page 5.
 Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3540261826 . Electronic edition, page 17.
Categories: Parametric families of graphs
Wikimedia Foundation. 2010.
Look at other dictionaries:
Bipartite graph — In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V ; that is, U and V are independent sets.… … Wikipedia
Complete graph — K7, a complete graph with 7 vertices Vertices n Edges … Wikipedia
Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges … Wikipedia
Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
Graph isomorphism — In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly… … Wikipedia
Bipartite dimension — In the mathematical field of graph theory, the bipartite dimension of an graph G=(V,E) is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is … Wikipedia
Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor … Wikipedia
graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… … Universalium
Complete coloring — of the Clebsch graph with 8 colors. Every pair of colors appears on at least one edge. No complete coloring with more colors exists: in any 9 coloring some color would appear only at one vertex, and there would not be enough neighboring vertices… … Wikipedia
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia
16+© Academic, 20002019 Contact us: Technical Support, Advertising
Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx.Share the article and excerpts
We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.
Complete bipartite graph
 Complete bipartite graph

Complete bipartite graph
A complete bipartite graph with m = 5 and n = 3Vertices n + m Edges mn Girth 4 Automorphisms 2m!n! if m=n, otherwise m!n! Chromatic number 2 Chromatic index max{m, n} Notation K_{m,n}