Turán graph

From Wikipedia, the free encyclopedia

The Turán graph T(13,4).

The Turán graph T(n,r) is a graph formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and connecting two vertices by an edge whenever they belong to different subsets. The graph will have $(n mod r)$ subsets of size $\lceil n/r\rceil$ , and $r - (n mod r)$ subsets of size $\lfloor n/r\rfloor$ . Each vertex has degree either $n-\lceil n/r\rceil$ or $n-\lfloor n/r\rfloor$ . The number of edges is

$\left\lfloor\left(1-\frac1r\right)\frac{n^2}{2}\right\rfloor.$

Turán graphs are named after P. Turán, who used them to prove Turán's theorem.

1 Properties and applications
2 References
3 External links
4 See also

[edit] Properties and applications

Every Turán graph is a cograph. The Turán graph T(n,2) is a complete bipartite graph and, when n is even, a Moore graph. When r is a divisor of n, the Turán graph is symmetric and strongly regular, although some authors consider Turán graphs to be a trivial case of strongly regularity and therefore exclude them from the definition of a strongly regular graph.

By the pigeonhole principle, any set of r+1 vertices in the Turán graph includes two vertices in the same partition subset; therefore, the Turán graph does not contain a clique of size r+1. According to Turán's theorem, the Turán graph has the maximum possible number of edges among all (r+1)-clique-free graphs. Keevash and Sudakov (2003) show that the Turán graph is also the only (r+1)-clique-free graph of order n in which every subset of αn vertices spans at least $\frac{r\,{-}\,1}{2r}(2\alpha -1)n^2$ edges.

The Turán graph $T(n,\lceil n/3\rceil)$ has 3^a2^b maximal cliques, where 3a+2b=n and b≤2; each maximal clique is formed by choosing one vertex from each partition subset. This is the largest number of maximal cliques possible among all n-vertex graphs regardless of the number of edges in the graph (Moon and Moser 1965); these graphs are sometimes called Moon-Moser graphs.

Chao and Novacky (1982) show that the Turán graphs are chromatically unique: no other graphs have the same chromatic polynomials. Nikiforov (2005) uses Turán graphs to supply a lower bound for the sum of the kth eigenvalues of a graph and its complement.

Falls, Powell, and Snoeyink develop an efficient algorithm for finding clusters of orthologous groups of genes in genome data, by representing the data as a graph and searching for large Turán subgraphs.

Turán graphs also have some interesting properties related to geometric graph theory. Pór and Wood (2005) give a lower bound of Ω((rn)^3/4) on the volume of any three-dimensional grid embedding of the Turán graph. Witsenhausen (1974) conjectures that the maximum sum of squared distances, among n points with unit diameter in R^d, is attained for a configuration formed by embedding a Turán graph onto the vertices of a regular simplex. The 1-skeleton of a d-dimensional cross-polytope is a Turán graph T(2d,d), and is also called the cocktail-party graph.

[edit] References

Chao, C. Y.; Novacky, G. A. (1982). "On maximally saturated graphs". Discrete Mathematics 41: 139–143.

Falls, Craig; Powell, Bradford; Snoeyink, Jack. "Computing high-stringency COGs using Turán type graphs".

Keevash, Peter; Sudakov, Benny (2003). "Local density in graphs with forbidden subgraphs". Combinatorics, Probability and Computing 12: 139–153.

Moon, J. W.; Moser, L. (1965). "On cliques in graphs". Israel Journal of Mathematics 3: 23–28.

Nikiforov, Vladimir (2005). "Eigenvalue problems of Nordhaus-Gaddum type". arXiv:math.CO/0506260.

Pór, Attila; Wood, David R. (2005). "No-three-in-line-in-3D". Graph Drawing, 395–402, Lecture Notes in Computer Science no. 3383, Springer-Verlag. DOI:10.1007/b105810.