Turán graph

From Wikipedia, the free encyclopedia

Turán graph
The Turán graph T(13,4)
Named after	Pál Turán
This box: view • talk • edit

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$ . That is, it is a complete k-partite graph

$K_{\lceil n/r\rceil, \lceil n/r\rceil, \ldots, \lfloor n/r\rfloor, \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ál 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; that is, it can be formed from individual vertices by a sequence of disjoint union and complement operations. Specifically, such a sequence can begin by forming each of the independent sets of the Turán graph as a disjoint union of isolated vertices. Then, the overall graph is the complement of the disjoint union of the complements of these independent sets.

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, if α is sufficiently close to 1. The Erdős–Stone theorem extends Turán's theorem by bounding the number of edges in a graph that does not have a fixed Turán graph as a subgraph. Via this theorem, similar bounds in extremal graph theory can be proven for any excluded subgraph, depending on the chromatic number of the subgraph.

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.

The Turán graph T(2n,n) can be formed by removing a perfect matching from a complete graph K_2n. As Roberts (1969) showed, this graph has boxicity exactly n; for this reason, it is sometimes known as the Roberts graph.

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. doi:10.1016/0012-365X(82)90200-X.

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. doi:10.1017/S0963548302005539.

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". Proc. Int. Symp. Graph Drawing (GD 2004): 395–402, Lecture Notes in Computer Science no. 3383, Springer-Verlag. doi:10.1007/b105810.