Complete bipartite graph

Complete bipartite graph
A complete bipartite graph with m = 5 and n = 3
Vertices	n + m
Edges	mn
Radius	$\left\{\begin{array}{ll}1 & m = 1 \vee n = 1\\ 2 & \text{otherwise}\end{array}\right.$
Diameter	$\left\{\begin{array}{ll}1 & m = n = 1\\ 2 & \text{otherwise}\end{array}\right.$
Girth	$\left\{\begin{array}{ll}\infty & m = 1 \vee n = 1\\ 4 & \text{otherwise}\end{array}\right.$
Automorphisms	$\left\{\begin{array}{ll}2 m! n! & n = m\\ m! n! & \text{otherwise}\end{array}\right.$
Chromatic number	2
Chromatic index	max{m, n}
Spectrum	$\{0^{n + m - 2}, (\pm \sqrt{n m})^1\}$
Notation	$K_{m,n}$

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.^[1][2]

Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher.^[3][4] Llull himself had made similar drawings of complete graphs three centuries earlier.^[3]

Definition

A complete bipartite graph is a graph whose vertices can be partitioned into two subsets V₁ and V₂ such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph (V₁, V₂, E) such that for every two vertices v₁ ∈ V₁ and v₂ ∈ V₂, v₁v₂ is an edge in E. A complete bipartite graph with partitions of size |V₁|=m and |V₂|=n, is denoted K_m,n;^[1][2] every two graphs with the same notation are isomorphic.

Examples

The star graphs S₃, S₄, S₅ and S₆.

The utility graph K_3,3

• For any k, K_1,k is called a star.^[2] All complete bipartite graphs which are trees are stars.
• The graph K_1,3 is called a claw, and is used to define the claw-free graphs.^[5]
• 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.^[6]

Properties

• Given a bipartite graph, testing whether it contains a complete bipartite subgraph K_i,i for a parameter i is an NP-complete problem.^[7]
• 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). Conversely, every nonplanar graph contains either K_3,3 or the complete graph K₅ as a minor; this is Wagner's theorem.^[8]
• Every complete bipartite graph. K_n,n is a Moore graph and a (n,4)-cage.^[9]
• The complete bipartite graphs K_n,n and K_n,n+1 have the maximum possible number of edges among all triangle-free graphs with the same number of vertices; this is Mantel's theorem. Mantel's result was generalized to k-partite graphs and graphs that avoid larger cliques as subgraphs in Turán's theorem, and these two complete bipartite graphs are examples of Turán graphs, the extremal graphs for this more general problem.^[10]
• The complete bipartite graph K_m,n has a vertex covering number of min{m,n} and an edge covering number of max{m,n}.
• The 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.^[11]
• 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^m−1 spanning trees.^[12]
• 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 n-edge-coloring corresponding to a Latin square.^[13]

See also

• Biclique-free graph, a class of sparse graphs defined by avoidance of complete bipartite subgraphs
• Crown graph, a graph formed by removing a perfect matching from a complete bipartite graph
• Complete multipartite graph, a generalization of complete bipartite graphs to more than two sets of vertices

References

1. Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 5, ISBN 0-444-19451-7.
2. Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 17.
3. Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J., Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37.
4. Read, Ronald C.; Wilson, Robin J. (1998), An Atlas of Graphs, Clarendon Press, p. ii, ISBN 9780198532897.
5. Lovász, László; Plummer, Michael D. (2009), Matching theory, AMS Chelsea Publishing, Providence, RI, p. 109, ISBN 978-0-8218-4759-6, MR 2536865. Corrected reprint of the 1986 original.
6. Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer, p. 437, ISBN 9780387941158.
7. Garey, Michael R.; Johnson, David S. (1979), "[GT24] Balanced complete bipartite subgraph", Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, p. 196, ISBN 0-7167-1045-5.
8. Diestel, elect. ed. p. 105.
9. Biggs, Norman (1993), Algebraic Graph Theory, Cambridge University Press, p. 181, ISBN 9780521458979.
10. Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, p. 104, ISBN 9780387984889.
11. Bollobás (1998), p. 266.
12. Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematic 5, Springer, p. 557, ISBN 9783642322785.
13. Jensen, Tommy R.; Toft, Bjarne (2011), Graph Coloring Problems, Wiley Series in Discrete Mathematics and Optimization 39, John Wiley & Sons, p. 16, ISBN 9781118030745.