Complete bipartite graph

Complete bipartite graph
A complete bipartite graph with m = 5 and n = 3
Verticesn + m
Edgesmn
Radius
Diameter
Girth
Automorphisms
Chromatic number2
Chromatic indexmax{m, n}
Spectrum
NotationK{m,n}
Table of graphs and parameters

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]

  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. ^ a b Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN 0191630624.
  4. ^ Read, Ronald C.; Wilson, Robin J. (1998), An Atlas of Graphs, Clarendon Press, p. ii, ISBN 9780198532897.