TURáN GRAPH

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 subsets of size $lceil\; n/r$
ceil, and subsets of size $lfloor\; n/r$
floor. That is, it is a complete ''k''-partite graph
:$K\_\{lceil\; n/r$
ceil, lceil n/r
ceil, ldots, lfloor n/r
floor, lfloor n/r
floor}.
Each vertex has degree either $n-lceil\; n/r$
ceil or $n-lfloor\; n/r$
floor. The number of edges is
:
ight)rac{n^2}{2}
ight
floor.
Turán graphs are named after Pál Turán, who used them to prove Turán's theorem.

Contents

Properties and applications

References

External links

See also

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 edges. 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$
ceil) has 3^''a''2^''b'' maximal cliques, where
3''a''+2''b''=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''(2''n'',''n'') can be formed by removing a perfect matching from a complete graph ''K''_2''n''. As 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 ''k''th 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''(2''d'',''d''), and is also called the ''cocktail-party graph''.

References

★ On maximally saturated graphs, Chao, C. Y.; Novacky, G. A., , , Discrete Mathematics, 1982

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

★ Local density in graphs with forbidden subgraphs, Keevash, Peter; Sudakov, Benny, , , Combinatorics, Probability and Computing, 2003

★

★ {{cite journal
| author = Nikiforov, Vladimir
| title = Eigenvalue problems of Nordhaus-Gaddum type
| year = 2005
| id =

★

★ .

★ On an extremal problem in graph theory, Turan, P., , , Matematiko Fizicki Lapok, 1941

★ On the maximum of the sum of squared distances under a diameter constraint, Witsenhausen, H. S., , , American Mathematical Monthly, 1974

External links

★

★

See also

★ Complete bipartite graph

★ Turán's theorem

★ Extremal graph theory