Turán Graph

A Turán graph, sometimes called a maximally saturated graph (Zykov 1952, Chao and Novacky 1982), with positive integer parameters and is a type of extremal graph on vertices originally considered by Turán (1941). There are unfortunately two different conventions for the index .

In the more standard terminology (and that adopted here), the -Turán graph, sometimes also called a K-graph and variously denoted , (Gross and Yellen 2006, p. 476), (Chao and Novacky 1982), or (Pach and Agarwal 1995, p. 120), is the extremal graph on graph vertices that contains no -clique for (Chao and Novacky 1982; Diestel 1997, p. 149; Bollobás 1998, p. 108). In other words, the Turán graph has the maximum possible number of graph edges of any -vertex graph not containing a complete graph . The Turán graph is also the complete -partite graph on vertices whose partite sets are as nearly equal in cardinality as possible (Gross and Yellen 2006, p. 476).

Unfortunately, some authors, including Skiena (1990, pp. 143-144), Aigner (1995), and Pemmaraju and Skiena (2003, pp. 247-248), use the convention that the -Turán graph contains no -clique (instead of -clique), meaning that the -Turán graph of these authors is the -Turán graph as defined above.

The Turán graph on vertices that does not contain the complete graph can be generated in the Wolfram Language using TuranGraph[n, k] and precomputed properties are available using GraphData["Turan", n, k].

Turán graphs may be obtained by dividing a set of graph vertices into pairwise disjoint subsets with graph vertices of degree , ..., , satisfying

(1)

and with two graph vertices joined iff they lie in distinct graph vertex sets. Such graphs are sometimes denoted .

They can be directly constructed by numbering the vertices 0, 1, ..., and connecting vertices by an edge iff when the vertices are incongruent modulo (König 1936, Chao and Novacky 1982).

Turán's theorem gives the number of edges for the -Turán graph as

(2)

where denotes the floor function. This gives the triangle

(3)

(OEIS A193331).

Turán graphs are chromatically unique (Chao and Novacky 1982). A Turán graph is always strongly regular if (but may be regular even if ).

The chromatic number of is (Chao and Novacky 1982).

Special cases of Turán graphs are summarized in the following table.

graph class	Turán graph
complete graph
complete bipartite graph
-cocktail party graph
complete tripartite graph
empty graph

The Turán graph has maximal cliques where and , the largest number possible among all -vertex graphs (Moon and Moser 1965).