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