complete bipartite graph


Also found in: Wikipedia.

complete bipartite graph

[kəm¦plēt bī′pär‚tīt ‚graf]
(mathematics)
A graph whose vertices can be partitioned into two sets such that every edge joins a vertex in one set with a vertex in the other, and each vertex in one set is joined to each vertex in the other by exactly one edge.
Mentioned in ?
References in periodicals archive ?
Such colored matrix can be considered as a factorization of the complete bipartite graph [K.sub.n,m].
For example, consider a complete bipartite graph [K.sub.r,s] with partite sets U and V.
For a complete bipartite graph G = (V, E, w) with n vertices, we have
Complete Bipartite Graph. Given a graph G = (V;E), where V denotes a set of vertices and E denotes a set of edges connecting pairs of vertices, if the set V can be divided into two disjoint and nonempty sets, X and Y, that is, V = X [union] Y and X [intersection] Y = [PHI], where [PHI] denotes the empty set, every edge in E connects one vertex in X to another vertex in Y, and no edge connects two vertices of the same set, we call G a complete bipartite graph.
For every complete bipartite graph [K.sub.r,t] and every k [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],
For instance, the complete bipartite graph [K.sub.m,n] and wheel graph [W.sub.n] are 2-distance balanced, but not distance balanced.
The super subdivision graph S (G) is obtained from G by replacing every edge e of G by a complete bipartite graph K2,m (m 2) in such a way that the ends of e are merged with the two vertices of the 2-vertices part of K2,m after removing the edge e from G.
Consider a complete bipartite graph [K.sub.m, n] with a bipartition {U, W} where U = {[u.sub.1], [u.sub.2], ..., [u.sub.m]} and W = {[w.sub.1], [w.sub.2], ..., [w.sub.n]}.
Let [K.sub.r,s] be a complete bipartite graph. Then
A graph H is called a supersubdivision of G if H is obtained from G by replacing every edge [e.sub.i] of G by a complete bipartite graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [m.sub.i], 1 [less than or equal to] i [less than or equal to] q in such a way that the end vertices of each [e.sub.i] are identified with the two vertices of 2-vertices part of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] after removing the edge [e.sub.i] from graph G.
In a bipartite graph, if every vertex of U is adjacent to every vertex of V, then such graph is called complete bipartite graph. A complete bipartite graph with [absolute value of U]= [a-z] and [absolute value of V]= [a-z] is denoted by [K.sub.s, t].
Let G = [K.sub.m,n,] m [less than or equal to] n be a complete bipartite graph with m + n = p.

Full browser ?