Turán Graph
   HOME

TheInfoList



OR:

The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where q and s are the quotient and remainder of dividing n by r (so n = qr + s), the graph is of the form K_, and the number of edges is : \left(1 - \frac\right)\frac + . For r\le7, this edge count can be more succinctly stated as \left\lfloor\left(1-\frac1r\right)\frac2\right\rfloor. The graph has s subsets of size q+ 1 , and r - s subsets of size q; each vertex has degree n-q-1 or n-q. It is a
regular graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...
if n is divisible by r (i.e. when s=0).


Turán's theorem

Turán graphs are named after
Pál Turán Pál Turán (; 18 August 1910 – 26 September 1976) also known as Paul Turán, was a Hungarian mathematician who worked primarily in extremal combinatorics. In 1940, because of his Jewish origins, he was arrested by History of the Jews in Hun ...
, who used them to prove Turán's theorem, an important result in
extremal graph theory Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence loca ...
. By the pigeonhole principle, every 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. 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(2\alpha -1)n^2 edges, if α is sufficiently close to 1. The
Erdős–Stone theorem In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán's theorem to bound the number of edges in an ''H''-free graph for a non-complete graph ''H''. It is named after Paul Erdős and Arthur Stone (mathemati ...
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 In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
of the subgraph.


Special cases

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''(2''n'',''n'') can be formed by removing a
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
from a
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
''K''2''n''. As showed, this graph has boxicity exactly ''n''; it is sometimes known as the ''Roberts graph''. This graph is also the 1-
skeleton A skeleton is the structural frame that supports the body of most animals. There are several types of skeletons, including the exoskeleton, which is a rigid outer shell that holds up an organism's shape; the endoskeleton, a rigid internal fra ...
of an ''n''-dimensional
cross-polytope In geometry, a cross-polytope, hyperoctahedron, orthoplex, staurotope, or cocube is a regular, convex polytope that exists in ''n''- dimensional Euclidean space. A 2-dimensional cross-polytope is a square, a 3-dimensional cross-polytope is a reg ...
; for instance, the graph ''T''(6,3) = ''K''2,2,2 is the octahedral graph, the graph of the regular
octahedron In geometry, an octahedron (: octahedra or octahedrons) is any polyhedron with eight faces. One special case is the regular octahedron, a Platonic solid composed of eight equilateral triangles, four of which meet at each vertex. Many types of i ...
. 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 In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...
and, when ''n'' is even, a Moore graph. When ''r'' is a divisor of ''n'', the Turán graph is
symmetric Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
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 class of Turán graphs can have exponentially many maximal cliques, meaning this class does not have few cliques. For example, the Turán graph T(n,\lceil n/3\rceil) 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; 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 In mathematics, the disjoint union (or discriminated union) A \sqcup B of the sets and is the set formed from the elements of and labelled (indexed) with the name of the set from which they come. So, an element belonging to both and appe ...
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. 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
eigenvalue In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...
s of a graph and its complement. 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 Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geomet ...
. give a lower bound of Ω((''rn'')3/4) on the volume of any three-dimensional grid embedding of the Turán graph. 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. 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.


Notes


References

* * * * * * * * *


External links

* * * {{DEFAULTSORT:Turan graph Parametric families of graphs Extremal graph theory