Complete bipartite graph | |
---|---|

Vertices | n + m |

Edges | mn |

Radius | |

Diameter | |

Girth | |

Automorphisms | |

Chromatic number | 2 |

Chromatic index | max{m, n} |

Spectrum | |

Notation | |

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] }

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

- For any
*k*,*K*_{1,k}is called a star.^{ [2] }All complete bipartite graphs which are trees are stars.- The graph
*K*_{1,3}is called a claw, and is used to define the claw-free graphs.^{ [5] }

- The graph
- The graph
*K*_{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*K*_{3,3}.^{ [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.

K_{3,3} | K_{4,4} | K_{5,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 p^{2} 2-edges. They also can also be drawn as p edge-colorings. |

- Given a bipartite graph, testing whether it contains a complete bipartite subgraph
*K*_{i,i}for a parameter*i*is an NP-complete problem.^{ [8] } - A planar graph cannot contain
*K*_{3,3}as a minor; an outerplanar graph cannot contain*K*_{3,2}as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary). Conversely, every nonplanar graph contains either*K*_{3,3}or the complete graph*K*_{5}as a minor; this is Wagner's theorem.^{ [9] } - Every complete bipartite graph.
**K**_{n,n}is a Moore graph and a (*n*,4)-cage.^{ [10] } - The complete bipartite graphs
**K**_{n,n}and**K**_{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*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.^{ [11] } - The complete bipartite graph
**K**_{m,n}has a vertex covering number of**min**{*m*,*n*} and an edge covering number of**max**{*m*,*n*}. - The complete bipartite graph
**K**_{m,n}has a maximum independent set of size**max**{*m*,*n*}. - The adjacency matrix of a complete bipartite graph
**K**_{m,n}has eigenvalues √*nm*, −√*nm*and 0; with multiplicity 1, 1 and*n*+*m*−2 respectively.^{ [12] } - The Laplacian matrix of a complete bipartite graph
**K**_{m,n}has eigenvalues*n*+*m*,*n*,*m*, and 0; with multiplicity 1,*m*−1,*n*−1 and 1 respectively. - A complete bipartite graph
**K**_{m,n}has*m*^{n−1}*n*^{m−1}spanning trees.^{ [13] } - A complete bipartite graph
**K**_{m,n}has a maximum matching of size**min**{*m*,*n*}. - A complete bipartite graph
**K**_{n,n}has a proper*n*-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] }

- Biclique-free graph, a class of sparse graphs defined by avoidance of complete bipartite subgraphs
- Crown graph, a graph formed by removing a perfect matching from a complete bipartite graph
- Complete multipartite graph, a generalization of complete bipartite graphs to more than two sets of vertices
- Biclique attack

In graph theory, a **planar graph** is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a **plane graph** or **planar embedding of the graph**. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In graph theory, a **tree** is an undirected graph in which any two vertices are connected by *exactly one* path, or equivalently a connected acyclic undirected graph. A **forest** is an undirected graph in which any two vertices are connected by *at most one* path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

In the mathematical field of graph theory, a **bipartite graph** is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . Vertex sets and are usually called the *parts* of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

Informally, the **reconstruction conjecture** in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

This is a **glossary of graph theory**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an **outerplanar graph** is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

In graph theory, an undirected graph *H* is called a **minor** of the graph *G* if *H* can be formed from *G* by deleting edges and vertices and by contracting edges.

**Extremal graph theory** is a branch of mathematics that studies how global properties of a graph influence local substructure. It encompasses a vast number of results that describe how certain graph properties - number of vertices (size), number of edges, edge density, chromatic number, and girth, for example - guarantee the existence of certain local substructures.

In the mathematical discipline of graph theory, a **matching** or **independent edge set** in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

In graph theory, the **degree** of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The **maximum degree** of a graph , denoted by , and the **minimum degree** of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

In graph theory, the **Hadwiger conjecture** states that if G is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

In mathematics, a **dense graph** is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a **sparse graph**. The distinction between sparse and dense graphs is rather vague, and depends on the context.

In graph theory, a **factor** of a graph *G* is a spanning subgraph, i.e., a subgraph that has the same vertex set as *G*. A ** k-factor** of a graph is a spanning

The **Zarankiewicz problem**, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size. It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951.

In graph theory, an **adjacent vertex** of a vertex *v* in a graph is a vertex that is connected to *v* by an edge. The **neighbourhood** of a vertex *v* in a graph *G* is the subgraph of *G* induced by all vertices adjacent to *v*, i.e., the graph composed of the vertices adjacent to *v* and all edges connecting vertices adjacent to *v*. For example, in the image to the right, the neighbourhood of vertex 5 consists of vertices 1, 2 and 4 and the edge connecting vertices 1 and 2.

In graph theory, a **rook's graph** is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge represents a legal move from one square to another. The same graphs can be defined mathematically as the Cartesian products of two complete graphs or as the line graphs of complete bipartite graphs.

In graph theory, a branch of mathematics, a **crown graph** on 2*n* vertices is an undirected graph with two sets of vertices {*u*_{1}, *u*_{2}, ..., *u*_{n}} and {*v*_{1}, *v*_{2}, ..., *v*_{n}} and with an edge from *u*_{i} to *v*_{j} whenever *i* ≠ *j*.

In graph theory, an area of mathematics, an **equitable coloring** is an assignment of colors to the vertices of an undirected graph, in such a way that

In the mathematical study of graph theory, a **pancyclic graph** is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

In graph theory, a branch of mathematics, a t-**biclique-free** graph is a graph that has no 2t-vertex complete bipartite graph *K*_{t,t} as a subgraph. A family of graphs is biclique-free if there exists a number t such that the graphs in the family are all t-biclique-free. The biclique-free graph families form one of the most general types of sparse graph family. They arise in incidence problems in discrete geometry, and have also been used in parameterized complexity.

- 1 2 Bondy, John Adrian; Murty, U. S. R. (1976),
*Graph Theory with Applications*, North-Holland, p. 5, ISBN 0-444-19451-7 . - 1 2 3 Diestel, Reinhard (2005),
*Graph Theory*(3rd ed.), Springer, ISBN 3-540-26182-6 . Electronic edition, page 17. - 1 2 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 . - ↑ Read, Ronald C.; Wilson, Robin J. (1998),
*An Atlas of Graphs*, Clarendon Press, p. ii, ISBN 9780198532897 . - ↑ Lovász, László; Plummer, Michael D. (2009),
*Matching theory*, Providence, RI: AMS Chelsea, p. 109, ISBN 978-0-8218-4759-6, MR 2536865 . Corrected reprint of the 1986 original. - ↑ Gries, David; Schneider, Fred B. (1993),
*A Logical Approach to Discrete Math*, Springer, p. 437, ISBN 9780387941158 . - ↑ Coxeter,
*Regular Complex Polytopes*, second edition, p.114 - ↑ 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 . - ↑ Diestel 2005 , p. 105
- ↑ Biggs, Norman (1993),
*Algebraic Graph Theory*, Cambridge University Press, p. 181, ISBN 9780521458979 . - ↑ Bollobás, Béla (1998),
*Modern Graph Theory*, Graduate Texts in Mathematics,**184**, Springer, p. 104, ISBN 9780387984889 . - ↑ Bollobás (1998), p. 266.
- ↑ Jungnickel, Dieter (2012),
*Graphs, Networks and Algorithms*, Algorithms and Computation in Mathematic,**5**, Springer, p. 557, ISBN 9783642322785 . - ↑ Jensen, Tommy R.; Toft, Bjarne (2011),
*Graph Coloring Problems*, Wiley Series in Discrete Mathematics and Optimization,**39**, Wiley, p. 16, ISBN 9781118030745 . - ↑ Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Absolute retracts of bipartite graphs",
*Discrete Applied Mathematics*,**16**(3): 191–215, doi: 10.1016/0166-218X(87)90058-8 , MR 0878021 .

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.