Turan Graph

Article Index for
Turan

Website Links For
Graph

Information About

Turan Graph

One can think about this graph as a process: First one takes place for the ''r'' parts. And then, one allocate the vertices to this parts in equal size (or almost equal size). The size of each part is floor or ceil of ''n''/''r''. Then one adds all the edges between each pair of vertices which belongs to a different part.

So the total number of edges is

:

e(T(rt,r)) = rac{rt \cdot (r-1)t}{2} = rac{r-1}{r} \cdot rac{n^2}{2}

with ''n'' = ''rt''.

Clearly, the Turán graph ''T''(''n'',''r'') does not contain a Clique of size ''r+1''. This is the best possible (with respect to the number of edges) among all graphs with ''n'' vertices (see Turán's Theorem ).

SEE ALSO

Turán's Theorem

Extremal Graph Theory