Complete bipartite graph
Encyclopedia
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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a complete bipartite graph or biclique is a special kind of bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
where every vertex
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
of the first set is connected to every vertex of the second set.
Definition
A complete bipartite graph, G := (V1 + V2, E), is a bipartite graph such that for any two vertices, v1 ∈ V1 and v2 ∈ V2, v1v2 is an edge in G. The complete bipartite graph with partitions of size |V1|=m and |V2|=n, is denoted Km,n.Examples
- For any k, K1,k is called a starStar (graph theory)In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...
. All complete bipartite graphs which are treesTree (graph theory)In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
are stars. - The graph K1,3 is called a clawClaw (graph theory)In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.A claw is another name for the complete bipartite graph K1,3...
, and is used to define the claw-free graphs. - The graph K3,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 nonplanarityPlanar graphIn 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...
of K3,3.
Properties
- Given a bipartite graph, finding its complete bipartite subgraph Km,n with maximal number of edges mn is an NP-completeNP-completeIn computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem. - A planar graphPlanar graphIn 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...
cannot contain K3,3 as a minorMinor (graph theory)In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
; an outerplanar graphOuterplanar graphIn graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
cannot contain K3,2 as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary). - A complete bipartite graph. Kn,n is a Moore graph and a (n,4)-cageCage (graph theory)In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.Formally, an -graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. It is known that an -graph exists...
. - A complete bipartite graph Kn,n or Kn,n+1 is a Turán graphTurán graphThe Turán graph T is a graph formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and connecting two vertices by an edge whenever they belong to different subsets. The graph will have subsets of size \lceil n/r\rceil, and r- subsets of size \lfloor n/r\rfloor...
. - A complete bipartite graph Km,n has a vertex covering number of min{m,n} and an edge covering number of max{m,n}.
- A complete bipartite graph Km,n has a maximum independent set of size max{m,n}.
- The adjacency matrix of a complete bipartite graph Km,n has eigenvalues √(nm), −√(nm) and 0; with multiplicity 1, 1 and n+m−2 respectively.
- The laplacian matrix of a complete bipartite graph Km,n has eigenvalues n+m, n, m, and 0; with multiplicity 1, m−1, n−1 and 1 respectively.
- A complete bipartite graph Km,n has mn−1 nm−1 spanning treeSpanning treeSpanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
s. - A complete bipartite graph Km,n has a maximum matching of size min{m,n}.
- A complete bipartite graph Kn,n has a proper n-edge-coloringEdge coloringIn graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
corresponding to a Latin squareLatin squareIn combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column...
. - The last two results are corollariesCorollaryA corollary is a statement that follows readily from a previous statement.In mathematics a corollary typically follows a theorem. The use of the term corollary, rather than proposition or theorem, is intrinsically subjective...
of the Marriage TheoremMarriage theoremIn mathematics, Hall's marriage theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets...
as applied to a k-regularRegular graphIn graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
bipartite graph.
See also
- Cycle graphCycle graphIn graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
- Path graphPath graphIn the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
- Crown graphCrown graphIn graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j...
- Complete graphComplete graphIn the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
- Null graphNull graphIn the mathematical field of graph theory, the null graph may refer either to the order zero graph, or alternatively, to any edgeless graph .-Order zero graph:...
- Adjacency matrixAdjacency matrixIn mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...