Complete bipartite graph

From Wikipedia, the free encyclopedia
(Redirected from Biclique)
Jump to navigation Jump to search

Template:Short description <templatestyles src="Infobox graph/styles.css"/>Script error: No such module "Infobox".Template:Template other

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 V1Script error: No such module "Check for unknown parameters". and V2Script error: No such module "Check for unknown parameters". 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)Script error: No such module "Check for unknown parameters". such that for every two vertices v1 ∈ V1Script error: No such module "Check for unknown parameters". and v2 ∈ V2Script error: No such module "Check for unknown parameters"., v1v2Script error: No such module "Check for unknown parameters". is an edge in Template:Mvar. A complete bipartite graph with partitions of size Template:Abs = mScript error: No such module "Check for unknown parameters". and Template:Abs = nScript error: No such module "Check for unknown parameters"., is denoted Km,nScript error: No such module "Check for unknown parameters".;[1][2] every two graphs with the same notation are isomorphic.

Examples

File:Star graphs.svg
The star graphs K1,3Script error: No such module "Check for unknown parameters"., K1,4Script error: No such module "Check for unknown parameters"., K1,5Script error: No such module "Check for unknown parameters"., and K1,6Script error: No such module "Check for unknown parameters"..
File:Zarankiewicz K4 7.svg
A complete bipartite graph of K4,7Script error: No such module "Check for unknown parameters". showing that Turán's brick factory problem with 4 storage sites (yellow spots) and 7 kilns (blue spots) requires 18 crossings (red dots)
  • For any Template:Mvar, K1,kScript error: No such module "Check for unknown parameters". is called a star.[2] All complete bipartite graphs which are trees are stars.
    • The graph K1,3Script error: No such module "Check for unknown parameters". is called a claw, and is used to define the claw-free graphs.[5]
  • The graph K3,3Script error: No such module "Check for unknown parameters". 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 K3,3Script error: No such module "Check for unknown parameters"..[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

Example Kp, pScript error: No such module "Check for unknown parameters". complete bipartite graphs[7]
K3,3Script error: No such module "Check for unknown parameters". K4,4Script error: No such module "Check for unknown parameters". K5,5Script error: No such module "Check for unknown parameters".
File:Complex polygon 2-4-3-bipartite graph.png File:Complex polygon 2-4-4 bipartite graph.png File:Complex polygon 2-4-5-bipartite graph.png
File:Complex polygon 2-4-3.png
3 edge-colorings 		File:Complex polygon 2-4-4.png
4 edge-colorings 		File:Complex polygon 2-4-5.png
5 edge-colorings
Regular complex polygons of the form 2{4}pScript error: No such module "Check for unknown parameters". have complete bipartite graphs with 2pScript error: No such module "Check for unknown parameters". vertices (red and blue) and p2Script error: No such module "Check for unknown parameters". 2-edges. They also can also be drawn as Template:Mvar edge-colorings.
  • Given a bipartite graph, testing whether it contains a complete bipartite subgraph Ki,iScript error: No such module "Check for unknown parameters". for a parameter Template:Mvar is an NP-complete problem.[8]
  • A planar graph cannot contain K3,3Script error: No such module "Check for unknown parameters". as a minor; an outerplanar graph cannot contain K3,2Script error: No such module "Check for unknown parameters". as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary). Conversely, every nonplanar graph contains either K3,3Script error: No such module "Check for unknown parameters". or the complete graph K5Script error: No such module "Check for unknown parameters". as a minor; this is Wagner's theorem.[9]
  • Every complete bipartite graph. Kn,nScript error: No such module "Check for unknown parameters". is a Moore graph and a (n,4)Script error: No such module "Check for unknown parameters".-cage.[10]
  • The complete bipartite graphs Kn,nScript error: No such module "Check for unknown parameters". and Kn,n+1Script error: No such module "Check for unknown parameters". 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 Template:Mvar-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.[11]
  • The complete bipartite graph Km,nScript error: No such module "Check for unknown parameters". has a vertex covering number of min{m, n} Script error: No such module "Check for unknown parameters". and an edge covering number of max{m, n}.Script error: No such module "Check for unknown parameters".
  • The complete bipartite graph Km,nScript error: No such module "Check for unknown parameters". has a maximum independent set of size max{m, n}.Script error: No such module "Check for unknown parameters".
  • The adjacency matrix of a complete bipartite graph Km,nScript error: No such module "Check for unknown parameters". has eigenvalues Template:RadicScript error: No such module "Check for unknown parameters"., −Template:RadicScript error: No such module "Check for unknown parameters". and 0; with multiplicity 1, 1 and n + m − 2Script error: No such module "Check for unknown parameters". respectively.[12]
  • The Laplacian matrix of a complete bipartite graph Km,nScript error: No such module "Check for unknown parameters". has eigenvalues n + mScript error: No such module "Check for unknown parameters"., Template:Mvar, Template:Mvar, and 0; with multiplicity 1, m − 1Script error: No such module "Check for unknown parameters"., n − 1Script error: No such module "Check for unknown parameters". and 1 respectively.
  • A complete bipartite graph Km,nScript error: No such module "Check for unknown parameters". has mn−1 nm−1Script error: No such module "Check for unknown parameters". spanning trees.[13]
  • A complete bipartite graph Km,nScript error: No such module "Check for unknown parameters". has a maximum matching of size min{m,n}.Script error: No such module "Check for unknown parameters".
  • A complete bipartite graph Kn,nScript error: No such module "Check for unknown parameters". has a proper [[edge coloring|Template:Mvar-edge-coloring]] corresponding to a Latin square.[14]
  • 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.[15]

See also

References

<templatestyles src="Reflist/styles.css" />

  1. ↑ a b Script error: No such module "citation/CS1"..
  2. ↑ a b c Script error: No such module "citation/CS1".. Electronic edition, page 17.
  3. ↑ a b Script error: No such module "citation/CS1"..
  4. ↑ Script error: No such module "citation/CS1"..
  5. ↑ Script error: No such module "citation/CS1".. Corrected reprint of the 1986 original.
  6. ↑ Script error: No such module "citation/CS1"..
  7. ↑ Coxeter, Regular Complex Polytopes, second edition, p.114
  8. ↑ Script error: No such module "citation/CS1"..
  9. ↑ Script error: No such module "Footnotes".
  10. ↑ Script error: No such module "citation/CS1"..
  11. ↑ Script error: No such module "citation/CS1"..
  12. ↑ Script error: No such module "Footnotes"., p. 266.
  13. ↑ Script error: No such module "citation/CS1"..
  14. ↑ Script error: No such module "citation/CS1"..
  15. ↑ Script error: No such module "citation/CS1"..

Script error: No such module "Check for unknown parameters".

Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=Complete_bipartite_graph&oldid=322599"