TOPICS
Search

Turán Graph


TuranGraph

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

In the more standard terminology (and that adopted here), the (n,k)-Turán graph, sometimes also called a K-graph and variously denoted T(n,k), T_(n,k) (Gross and Yellen 2006, p. 476), D(n,k) (Chao and Novacky 1982), or T_k(n) (Pach and Agarwal 1995, p. 120), is the extremal graph on n graph vertices that contains no (k+1)-clique for 1<=k<=n (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 n-vertex graph not containing a complete graph K_(k+1). The Turán graph is also the complete k-partite graph on n 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 (n,k)-Turán graph contains no k-clique (instead of (k+1)-clique), meaning that the T(n,k)-Turán graph of these authors is the (n,k-1)-Turán graph as defined above.

The Turán graph on n vertices that does not contain the complete graph K_(k+1) 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 {1,...,n} into k pairwise disjoint subsets with graph vertices of degree n_1, ..., n_k, satisfying

 n=n_1+...+n_k,
(1)

and with two graph vertices joined iff they lie in distinct graph vertex sets. Such graphs are sometimes denoted K_(n_1,...,n_k).

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

Turán's theorem gives the number of edges t(n,k) for the (n,k)-Turán graph as

 t(n,k)=|_((k-1)n^2)/(2k)_|,
(2)

where |_x_| denotes the floor function. This gives the triangle

 0
0 1
0 2 3
0 4 5 6
0 6 8 9 10
0 9 12 13 14 15
(3)

(OEIS A193331).

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

The chromatic number of T_(n,k) is k (Chao and Novacky 1982).

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

The Turán graph T(n,[n/3]) has 3^a2^b maximal cliques where 3a+2b=n and b<=2, the largest number possible among all n-vertex graphs (Moon and Moser 1965).


See also

Bipartite Graph, Clique, Complete Bipartite Graph, Complete Graph, Complete k-Partite Graph, k-Partite Graph, Extremal Graph, Extremal Graph Theory, Turán's Theorem

Explore with Wolfram|Alpha

References

Aigner, M. "Turán's Graph Theorem." Amer. Math. Monthly 102, 808-816, 1995.Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Bollobás, B. Modern Graph Theory. New York: Springer-Verlag, 1998.Chao, C. Y. and Novacky, G. A. Jr. "On Maximally Saturated Graphs." Disc. Math. 41, 139-143, 1982.Diestel, R. Graph Theory, 3rd ed. New York: Springer-Verlag, 1997.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 476-477, 2006.König, D. Theorie der endlichen under unendlichen Graphen. Leipzig, Germany: Akademic Verlag, 1936.Moon, J. W. and Moser, L. "On Cliques in Graphs." Israel J. Math. 3, 23-28, 1965.Pach, J. and Agarwal, P. K. Combinatorial Geometry. New York: Wiley, 1995.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 247-248, 2003.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 143 and 218, 1990.Sloane, N. J. A. Sequence A193331 in "The On-Line Encyclopedia of Integer Sequences."Turán, P. "On an Extremal Problem in Graph Theory." Mat. Fiz. Lapok 48, 436-452, 1941.Zykov, A. A. "On Some Properties of Linear Complexes." Mat. Sbornik N.S. 24, 163-188, 1949. Translation in Amer. Math. Soc. Transl., No. 79, 1-33, 1952.

Referenced on Wolfram|Alpha

Turán Graph

Cite this as:

Weisstein, Eric W. "Turán Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TuranGraph.html

Subject classifications