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

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

where denotes the floor function. This gives the triangle

(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.

The Turán graph has maximal cliques where and , the largest number possible among all -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.Turán, P. "On the Theorem of Graphs." Colloq. Math. 3, 19-30, 1954.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 Resource. https://mathworld.wolfram.com/TuranGraph.html

Subject classifications