Balanced Complete Multipartite Graph
A balanced complete multipartite graph is a complete multipartite graph whose partite sets all have the same cardinality. Equivalently, it is a complete multipartite graph of the form [画像:K_(n,...,n_()_(m))], also denoted K_(m×n).
The graph K_(m×n) has vertex count mn and edge count [画像:(m; 2)n^2]. It is (m-1)n-regular, has clique number and chromatic number equal to m, and has independence number n. Its graph complement is the disjoint union mK_n. For m>=2 and n>1, its graph diameter is 2.
When n=1, [画像:K_(m×1)=K_(1,...,1_()_(m))] is the complete graph on m vertices. Other special cases include balanced complete bipartite graphs K_(n,n) for m=2 and balanced complete tripartite graphs K_(n,n,n) for m=3.
For m>=2 and n>=1, every vertex of K_(m×n) has vertex transmission
| (m-1)n+2(n-1)=(m+1)n-2, |
so balanced complete multipartite graphs are transmission-regular.
See also
Chromatic Number, Clique Number, Complete Bipartite Graph, Complete Graph, Complete Multipartite Graph, Complete k-Partite Graph, Complete Tripartite Graph, Graph Complement, Graph Diameter, Independence Number, Regular Graph, Transmission-Regular Graph, Vertex TransmissionExplore with Wolfram|Alpha
More things to try:
Cite this as:
Weisstein, Eric W. "Balanced Complete Multipartite Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BalancedCompleteMultipartiteGraph.html