Complete bipartite graph

{{short description|Bipartite graph where each node of 1st set is linked to all nodes of 2nd set}}

{{infobox graph

| name = Complete bipartite graph

| image = 170px

| image_caption = A complete bipartite graph with {{math|1=m = 5}} and {{math|1=n = 3}}

| automorphisms = $\left\{\begin{array}{ll}2 m! n! & n = m\\ m! n! & \text{otherwise}\end{array}\right.$

| vertices = {{math|n + m}}

| edges = {{mvar|mn}}

| chromatic_number = 2

| chromatic_index = {{math|max{m, n} }}

| 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 \lor n = 1\\ 4 & \text{otherwise}\end{array}\right.$

| spectrum = $\left\{0^{n + m - 2}, (\pm\sqrt{nm})^1\right\}$

| notation = {{math|K{{sub|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.{{citation

| last1=Bondy

| first1=John Adrian

| author-link1=John Adrian Bondy

| last2=Murty

| first2=U. S. R.

| author-link2=U. S. R. Murty

| page=[https://archive.org/details/graphtheorywitha0000bond/page/5 5]

| title=Graph Theory with Applications

| year=1976

| publisher=North-Holland

| isbn=0-444-19451-7

| url=https://archive.org/details/graphtheorywitha0000bond/page/5

}}.{{Citation

| last=Diestel | first=Reinhard | author-link = Reinhard Diestel

| title=Graph Theory

| publisher=Springer

| year=2005

| edition=3rd

| isbn=3-540-26182-6

}}. [http://diestel-graph-theory.com/ Electronic edition], page 17.

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.{{citation|title=An Atlas of Graphs|first1=Ronald C.|last1=Read|first2=Robin J.|last2=Wilson|publisher=Clarendon Press|year=1998|isbn=9780198532897|page=ii}}. Llull himself had made similar drawings of complete graphs three centuries earlier.{{citation|contribution=Two thousand years of combinatorics|first=Donald E.|last=Knuth|author-link=Donald Knuth|pages=7–37|title=Combinatorics: Ancient and Modern|publisher=Oxford University Press|year=2013|editor1-first=Robin|editor1-last=Wilson|editor2-first=John J.|editor2-last=Watkins |contribution-url=https://books.google.com/books?id=vj1oAgAAQBAJ&pg=PA7 |isbn=978-0191630620}}.

Definition

A complete bipartite graph is a graph whose vertices can be partitioned into two subsets {{math|V{{sub|1}}}} and {{math|V{{sub|2}}}} 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 {{math|(V{{sub|1}}, V{{sub|2}}, E)}} such that for every two vertices {{math|v{{sub|1}} ∈ V{{sub|1}}}} and{{math| v{{sub|2}} ∈ V{{sub|2}}}}, {{math|v{{sub|1}}v{{sub|2}}}} is an edge in {{mvar|E}}. A complete bipartite graph with partitions of size {{math|1={{abs|V{{sub|1}}}} = m}} and {{math|1={{abs|V{{sub|2}}}} = n}}, is denoted {{math|K{{sub|m,n}}}}; every two graphs with the same notation are isomorphic.

Examples

File:Star graphs.svg {{math|K{{sub|1,3}}}}, {{math|K{{sub|1,4}}}}, {{math|K{{sub|1,5}}}}, and {{math|K{{sub|1,6}}}}.]]

File:Zarankiewicz K4 7.svg with 4 storage sites (yellow spots) and 7 kilns (blue spots) requires 18 crossings (red dots)]]

For any {{mvar|k}}, {{math|K{{sub|1,k}}}} is called a star. All complete bipartite graphs which are trees are stars.
The graph {{math|K{{sub|1,3}}}} is called a claw, and is used to define the claw-free graphs.{{citation | last1 = Lovász | first1 = László | author1-link = László Lovász | last2 = Plummer | first2 = Michael D. | author2-link = Michael D. Plummer | isbn = 978-0-8218-4759-6 | mr = 2536865 | page = 109 | publisher = AMS Chelsea |location=Providence, RI | title = Matching theory | url = https://books.google.com/books?id=yW3WSVq8ygcC&pg=PA109 | year = 2009}}. Corrected reprint of the 1986 original.
The graph {{math|K{{sub|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 {{math|K{{sub|3,3}}}}.{{citation|title=A Logical Approach to Discrete Math | first1=David|last1=Gries|author1-link=David Gries|first2=Fred B.|last2=Schneider|author2-link=Fred B. Schneider | publisher=Springer | year=1993|isbn=9780387941158|page=437|url=https://books.google.com/books?id=ZWTDQ6H6gsUC&pg=PA437}}.
The maximal bicliques found as subgraphs of the digraph of a relation are called concepts. When a lattice is formed by taking meets and joins of these subgraphs, the relation has an Induced concept lattice. This type of analysis of relations is called formal concept analysis.

Properties

class="wikitable skin-invert-image" align=right width=360

|+ Example {{math|K{{sub|p, p}}}} complete bipartite graphsCoxeter, Regular Complex Polytopes, second edition, p.114

! {{math|Thomsen graph}}

! {{math|K{{sub|4,4}}}}

! {{math|K{{sub|5,5}}}}

120px

|120px

align=center

|120px
3 edge-colorings

|120px
4 edge-colorings

|120px
5 edge-colorings

colspan=3|Regular complex polygons of the form {{math|2{4}p}} have complete bipartite graphs with {{math|2p}} vertices (red and blue) and {{math|p{{sup|2}}}} 2-edges. They also can also be drawn as {{mvar|p}} edge-colorings.

Given a bipartite graph, testing whether it contains a complete bipartite subgraph {{math|K{{sub|i,i}}}} for a parameter {{mvar|i}} is an NP-complete problem.{{citation

| last1=Garey

| first1=Michael R.

| author-link1=Michael R. Garey

| last2=Johnson

| first2=David S.

| author-link2=David S. Johnson

| contribution=[GT24] Balanced complete bipartite subgraph

| page=[https://archive.org/details/computersintract0000gare/page/196 196]

| year=1979

| title=Computers and Intractability: A Guide to the Theory of NP-Completeness

| publisher=W. H. Freeman

| isbn=0-7167-1045-5

}}.

A planar graph cannot contain {{math|K{{sub|3,3}}}} as a minor; an outerplanar graph cannot contain {{math|K{{sub|3,2}}}} as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary). Conversely, every nonplanar graph contains either {{math|K{{sub|3,3}}}} or the complete graph {{math|K{{sub|5}}}} as a minor; this is Wagner's theorem.{{harvnb|Diestel|2005|p=105}}
Every complete bipartite graph. {{math|K{{sub|n,n}}}} is a Moore graph and a {{math|(n,4)}}-cage.{{citation|title=Algebraic Graph Theory|first=Norman|last=Biggs|publisher=Cambridge University Press|year=1993|isbn=9780521458979|page=181|url=https://books.google.com/books?id=6TasRmIFOxQC&pg=PA181}}.
The complete bipartite graphs {{math|K{{sub|n,n}}}} and {{math|K{{sub|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 {{mvar|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.{{citation|title=Modern Graph Theory|volume=184|series=Graduate Texts in Mathematics|first=Béla|last=Bollobás|author-link=Béla Bollobás|publisher=Springer|year=1998|isbn=9780387984889|page=104|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA104}}.
The complete bipartite graph {{math|K{{sub|m,n}}}} has a vertex covering number of {{math|min{m, n} }} and an edge covering number of {{math|max{m, n}.}}
The complete bipartite graph {{math|K{{sub|m,n}}}} has a maximum independent set of size {{math|max{m, n}.}}
The adjacency matrix of a complete bipartite graph {{math|K{{sub|m,n}}}} has eigenvalues {{math|{{radic|nm}}}}, {{math|−{{radic|nm}}}} and 0; with multiplicity 1, 1 and {{math|n + m − 2}} respectively.{{harvtxt|Bollobás|1998}}, p. 266.
The Laplacian matrix of a complete bipartite graph {{math|K{{sub|m,n}}}} has eigenvalues {{math|n + m}}, {{mvar|n}}, {{mvar|m}}, and 0; with multiplicity 1, {{math|m − 1}}, {{math|n − 1}} and 1 respectively.
A complete bipartite graph {{math|K{{sub|m,n}}}} has {{math|m{{sup|n−1}} n{{sup|m−1}}}} spanning trees.{{citation|title=Graphs, Networks and Algorithms|volume=5|series=Algorithms and Computation in Mathematic|first=Dieter|last=Jungnickel|author-link=Dieter Jungnickel|publisher=Springer|year=2012|isbn=9783642322785|page=557|url=https://books.google.com/books?id=PrXxFHmchwcC&pg=PA557}}.
A complete bipartite graph {{math|K{{sub|m,n}}}} has a maximum matching of size {{math|min{m,n}.}}
A complete bipartite graph {{math|K{{sub|n,n}}}} has a proper edge coloring corresponding to a Latin square.{{citation|title=Graph Coloring Problems|volume=39|series=Wiley Series in Discrete Mathematics and Optimization|first1=Tommy R.|last1=Jensen|first2=Bjarne|last2=Toft|publisher=Wiley |year=2011|isbn=9781118030745|page=16|url=https://books.google.com/books?id=leL0Y5N0bFoC&pg=PA16}}.
Every complete bipartite graph is a modular graph: every triple of vertices has a median that belongs to shortest paths between each pair of vertices.{{citation

| last1 = Bandelt | first1 = H.-J.

| last2 = Dählmann | first2 = A.

| last3 = Schütte | first3 = H.

| doi = 10.1016/0166-218X(87)90058-8

| issue = 3

| journal = Discrete Applied Mathematics

| mr = 878021

| pages = 191–215

| title = Absolute retracts of bipartite graphs

| volume = 16

| year = 1987

| doi-access = free

}}.

References

Category:Parametric families of graphs

Complete bipartite graph

Definition

Examples

Properties

See also

References