edited by
972 views
1 votes
1 votes

A k partite graph is one where vertex set can be partitioned into k subsets so that no edge has both end in any one subset.

A complete k partite graph is one that is simple and in which each vertex is joined to every other vertex that is not in the same subset. The complete m-partite graph on n vertices in which each part has either floor(n/m) or ceil(n/m) vertices is denoted by Tm,n . Show that

a) | E(Tm,n) | = $\binom{n-k}{2} + (m-1)\binom{k+1}{2} , k = \left \lfloor n/m \right \rfloor$

b) If G is a complete m-partite graph on n vertices then | E(G) | <= | E(Tm,n)|, with equality only if G isomorphic to Tm,n

edited by

1 Answer

0 votes
0 votes

I am trying to answer the first part of the question.

The graph Tm,n specified in the question is a special type of graph known as Turan's graph. A Turan's graph is a complete m-partite graph where size of each partition differ by atmost 1.

No of vertices in Tm,n = n

No of partitions in Tm,n = m

Let

$n = am + b$

$n = am + b - ab + ab$

$n = b (a + 1) + (m - b) a$

So out of m partitions of Tm,n  b partitions have size a+1 and m-b partitions have size a.

No of possible pairs of vertices within the same partition is

$b\binom{a+1}{2} + (m-b)*\binom{a}{2}$

So total no of possible edges in Tm,n is

$\binom{n}{2} - (b\binom{a+1}{2} + (m-b)*\binom{a}{2})$

The answer is not complete. If someone know how to continue, please suggest.

(Note that a = k = floor(n/m))

Related questions

2 votes
2 votes
0 answers
2
1 votes
1 votes
1 answer
3
0 votes
0 votes
1 answer
4
gagan55 asked Jun 30, 2023
177 views
Number of hamiltonian cycles for a graph K 5, 5( bipartite graph ) ??