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 simple graph not containing a complete graph . The Turán graph is also the complete k-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 of cardinalities , ..., that differ by at most 1 and satisfy

(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 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 and denotes the floor function. This gives the number triangle

(3)

(OEIS A198787).

Turán graphs are chromatically unique (Chao and Novacky 1982). If , then the Turán graph is a balanced complete multipartite graph and hence is strongly regular unless , since is excluded by the convention used here. A Turán graph is regular iff .

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

Special cases of Turán graphs are summarized in the following table, where is a positive integer and in the row.

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

For , the Turán graph has maximal cliques, where and are nonnegative integers satisfying and . This is the largest number possible among all -vertex simple graphs (Moon and Moser 1965). The singleton graph has one maximal clique.