Complete bipartite graph

Complete bipartite graph

A complete bipartite graph with m = 5 and n = 3
Vertices n + m
Edges mn
Radius
Diameter
Girth
Automorphisms
Chromatic number 2
Chromatic index max{m, n}
Spectrum
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][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 V1 and V2 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 (V1, V2, E) such that for every two vertices v1V1 and v2V2, v1v2 is an edge in E. A complete bipartite graph with partitions of size |V1|=m and |V2|=n, is denoted Km,n;[1][2] every two graphs with the same notation are isomorphic.

Examples

The star graphs K1,3, K1,4, K1,5, and K1,6.

Properties

Example Kp,p complete bipartite graphs[7]
K3,3 K4,4 K5,5

3 edge-colorings

4 edge-colorings

5 edge-colorings
Regular complex polygons of the form 2{4}p have complete bipartite graphs with 2p vertices (red and blue) and p2 2-edges. They also can also be drawn as p edge-colorings.

See also

References

  1. 1 2 Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 5, ISBN 0-444-19451-7.
  2. 1 2 3 Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 17.
  3. 1 2 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. Coxeter, Regular Complex Polytopes, second edition, p.114
  8. 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.
  9. Diestel, elect. ed. p. 105.
  10. Biggs, Norman (1993), Algebraic Graph Theory, Cambridge University Press, p. 181, ISBN 9780521458979.
  11. Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, 184, Springer, p. 104, ISBN 9780387984889.
  12. Bollobás (1998), p. 266.
  13. Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematic, 5, Springer, p. 557, ISBN 9783642322785.
  14. Jensen, Tommy R.; Toft, Bjarne (2011), Graph Coloring Problems, Wiley Series in Discrete Mathematics and Optimization, 39, John Wiley & Sons, p. 16, ISBN 9781118030745.
  15. Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Absolute retracts of bipartite graphs", Discrete Applied Mathematics, 16 (3): 191–215, MR 878021, doi:10.1016/0166-218X(87)90058-8.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.