Main Page | See live article | Alphabetical index

Turán graph

In mathematical graph theory, the Turán graph for given natural numbers n and k, denoted T(n, k), is defined as the extremal graph with n vertices which does not contain the complete graph Kk as a subgraph. An upper bound for the number of edges of T(n, k), typically written as t(n, k), is given by Turán's theorem; as a special case, for k = 3, one obtains

Turán graphs were first described and studied by Hungarian mathematician Paul Turán.

Also see