Complete bipartite graph explained

Complete bipartite graph
Automorphisms:

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

| vertices = | edges = | chromatic_number = 2 | chromatic_index = | radius =

\left\{\begin{array}{ll}1&m=1\veen=1\ 2&otherwise\end{array}\right.

| diameter =

\left\{\begin{array}{ll}1&m=n=1\ 2&otherwise\end{array}\right.

| girth =

\left\{\begin{array}{ll}infty&m=1\lorn=1\ 4&otherwise\end{array}\right.

| spectrum =

\left\{0n,(\pm\sqrt{nm})1\right\}

| notation = }}

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] Llull himself had made similar drawings of complete graphs three centuries earlier.[4]

Definition

A complete bipartite graph is a graph whose vertices can be partitioned into two subsets and 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 such that for every two vertices and, is an edge in . A complete bipartite graph with partitions of size and, is denoted ; every two graphs with the same notation are isomorphic.

Examples

  • For any, is called a star. All complete bipartite graphs which are trees are stars.
  • The graph 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 .[6]
  • 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

See also

References

Notes and References

  1. .
  2. . Electronic edition, page 17.
  3. .
  4. .
  5. . Corrected reprint of the 1986 original.
  6. .
  7. Coxeter, Regular Complex Polytopes, second edition, p.114
  8. .
  9. .
  10. .
  11. , p. 266.
  12. .
  13. .
  14. .