2
$\begingroup$

A complete $k$-partite graph is a graph with disjoint sets of nodes where there is no edges between the nodes in same set, and there is an edge between any node and other nodes in the other subsets.

The subsets are $X_1,\dots,X_p$, and the number of nodes is $N$. What is the maximum number of edges that can be in this complete $k$-partite graph?

$\endgroup$
4
$\begingroup$

Divide up the vertices into your $k$ sets of sizes $a_{1}+...+a_{k}=N$ and consider a vertex in the first set. It has $a_{2}+...+a_{k}$ possible edges to make, therefore the contribution of the first disjoint set is $a_{1}(a_{2}+...+a_{k})$ edges. Since this first set has made as many edges as it may, we then 'ignore' these $a_{1}$ vertices and proceed in a similar fashion with the remaining disjoint sets. The total will amount to $a_{1}(a_{2}+...+a_{k})+a_{2}(a_{3}+...+a_{k})+...+a_{k-1}a_{k}$ edges.

If your sets are all of size $n/k$ then the total number of edges should at max be $\frac{n^{2}}{k^{2}}[(k-1)+(k-2)+...+1]=\frac{n^{2}(k-1)}{2k}$.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Is that mean that the number is max if we have $k$ = $N$ i.e. each subset has only one node ? $\endgroup$ – M.M Jun 1 '13 at 9:51
  • $\begingroup$ This is the case: of course when $k=N$ the graph is the complete graph on $N$ vertices. The final expression above becomes $\frac{n(n-1)}{2}$ edges. $\endgroup$ – Kaya Jun 1 '13 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.