Turán graph

Turán graph
The Turán graph T(13,4)
Named after	Pál Turán
v · regular graph, if n is divisible by r. Turán's theorem Turán graphs are named after Pál Turán, who used them to prove Turán's theorem, an important result in extremal graph theory. 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 with n vertices. 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. Special cases The octahedron, a cross polytope whose edges and vertices form a Turán graph T(6,3). Several choices of the parameter r in a Turán graph lead to notable graphs that have been independently studied. The Turán graph T(2n,n) can be formed by removing a perfect matching from a complete graph K2n. As Roberts (1969) showed, this graph has boxicity exactly n; it is sometimes known as the Roberts graph. This graph is also the 1-skeleton of an n-dimensional cross-polytope; for instance, the graph T(6,3) = K2,2,2 is the octahedral graph, the graph of the regular octahedron. If n couples go to a party, and each person shakes hands with every person except his or her partner, then this graph describes the set of handshakes that take place; for this reason it is also called the cocktail party graph. 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 strong regularity and therefore exclude them from the definition of a strongly regular graph. The Turán graph $T(n,\lceil n/3\rceil)$ has 3a2b 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. Other properties 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. 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 Rd, is attained for a configuration formed by embedding a Turán graph onto the vertices of a regular simplex. An n-vertex graph G is a subgraph of a Turán graph T(n,r) if and only if G admits an equitable coloring with r colors. The partition of the Turán graph into independent sets corresponds to the partition of G into color classes. In particular, the Turán graph is the unique maximal n-vertex graph with an r-color equitable coloring. References Chao, C. Y.; Novacky, G. A. (1982). "On maximally saturated graphs". Discrete Mathematics 41 (2): 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. http://www.cs.unc.edu/~snoeyink/comp145/cogs.pdf.  Keevash, Peter; Sudakov, Benny (2003). "Local density in graphs with forbidden subgraphs". Combinatorics, Probability and Computing 12 (2): 139–153. doi:10.1017/S0963548302005539.  Moon, J. W.; Moser, L. (1965). "On cliques in graphs". Israel Journal of Mathematics 3: 23–28. doi:10.1007/BF02760024.  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). Lecture Notes in Computer Science no. 3383, Springer-Verlag. pp. 395–402. doi:10.1007/b105810.  Roberts, F. S. (1969). "On the boxicity and cubicity of a graph". Recent Progress in Combinatorics. Academic Press. pp. 301–310.  Turán, P. (1941). "On an extremal problem in graph theory". Matematiko Fizicki Lapok 48: 436–452.  Witsenhausen, H. S. (1974). "On the maximum of the sum of squared distances under a diameter constraint". American Mathematical Monthly (The American Mathematical Monthly, Vol. 81, No. 10) 81 (10): 1100–1101. doi:10.2307/2319046. JSTOR 2319046.  External links Weisstein, Eric W., "Cocktail Party Graph" from MathWorld. Weisstein, Eric W., "Octahedral Graph" from MathWorld. Weisstein, Eric W., "Turán Graph" from MathWorld. Wikimedia Foundation. 2010. Игры ⚽ Поможем написать курсовую Arnulf I, Count of Flanders Lf Look at other dictionaries: Turán's theorem — In graph theory, Turán s theorem is a result on the number of edges in a Kr+1 free graph. An n vertex graph that does not contain any (r + 1) vertex clique may be formed by partitioning the set of vertices into r parts of equal or… …   Wikipedia Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia Turán number — In mathematics, the Turán number T( n , k , r ) for r graphs of order n is the smallest number of r edges such that every set of k vertices contains an edge. This number was determined for r = 2 by harvtxt|Turán|1941, and the problem for general… …   Wikipedia Pál Turán — Paul (Pál) Turán Born 18 August 1910 …   Wikipedia Satz von Turán — Der Satz von Turán (nach Pál Turán) ist eine Aussage aus dem mathematischen Teilgebiet der Graphentheorie. Er macht eine Aussage über die maximale Anzahl von Kanten, die ein Graph mit gegebener Knotenzahl haben kann, ohne einen vollständigen… …   Deutsch Wikipedia List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia Neighbourhood (graph theory) — A graph consisting of 6 vertices and 7 edges For other meanings of neighbourhoods in mathematics, see Neighbourhood (mathematics). For non mathematical neighbourhoods, see Neighbourhood (disambiguation). In graph theory, an adjacent vertex of a… …   Wikipedia Extremal graph theory — is a branch of mathematics. In the narrow sense, extremal graph theory studies the graphs which are extremal among graphs with a certain property. There are various meanings for the word extremal : with the largest number of edges, the largest… …   Wikipedia K-partiter Graph — Ein k partiter Graph ist in der Graphentheorie ein einfacher Graph, dessen Knotenmenge in k disjunkte Teilmengen zerfällt, sodass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Für k = 2 heißen diese Graphen bipartite… …   Deutsch Wikipedia Pál Turán — Pál Turán, 1955 Pál Turán (auch: Paul Turán; * 18. August 1910 in Budapest; † 26. September 1976 ebenda)[1] war ein u …   Deutsch Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”