Turan graph

Encyclopedia : T : TU : TUR : Turan graph

The Turán graph T(n,r) is the complete r-partite graph with n vertices whose partite sets differ in size at most 1.

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)) = \frac = \frac \cdot \frac ]

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).

Example

(a) Turan graph example for [T_3(7)]

Turan graph

Example

See also