Graphe de Turán

En théorie des graphes, un graphe de Turán (noté $T(n,r)$ ), aussi appelé maximally saturated graph, est un élément d'une famille de graphes qui portent le nom de Pál Turán.

graphe de Turán
Le graphe de Turan (13,4)

Notation	$T(n,r)$
Nombre de sommets	$n$
Nombre d'arêtes	~ ${\frac {(r-1)n^{2}}{2r}}$
Rayon	$\left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{otherwise}}\end{array}}\right.$
Diamètre	$\left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{sinon}}\end{array}}\right.$
Maille	$\left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{sinon}}\end{array}}\right.$
Nombre chromatique	$r$

Le graphe $T(n,r)$ possède $n$ sommets, partitionnés en $r$ sous-ensembles les plus équilibrés possibles, et chaque sommet est relié à tous les sommets qui ne sont pas dans son sous-ensemble. Par équilibré, on entend que le graphe a $(n{\text{ mod }}r)$ sous-ensembles de taille $\lceil n/r\rceil$ , et $r-(n{\text{ mod }}r)$ sous-ensembles de taille $\lfloor n/r\rfloor$ .

Définition

La graphe the Turán de paramètres n et r, noté $T(n,r)$ possède $n$ sommets, partitionnés en $r$ sous-ensembles les plus équilibrés possibles, et chaque sommet est relié à tous les sommets qui ne sont pas dans son sous-ensemble. Par équilibré, on entend que le graphe aura $(n{\text{ mod }}r)$ sous-ensembles de taille $\lceil n/r\rceil$ , et $r-(n{\text{ mod }}r)$ sous-ensembles de taille $\lfloor n/r\rfloor$ .

Propriétés

Le nombre chromatique du graphe $T(n,r)$ est r[1].

Cas particuliers et inclusions

L'octaèdre, dont les arêtes et les sommets forment K_2,2,2, un graphe Turán T(6,3). Les sommets non connectés ont la même couleur dans cette projection centrée sur les faces.

Les graphes bipartis complets sont des graphes de Turán.

Ce sont des cographes, c'est-à-dire qu'ils peuvent être formés par des unions disjointes et des passages au graphe complémentaire. On peut le faire de la manière suivante : pour chaque stable du graphe final, faire d'abord une union de tous les sommets, passer au complémentaire (dans chaque ensemble) pour avoir des cliques, puis faire l'union de toutes les cliques et passer encore au complémentaire.

Histoire

Les graphes de Turán portent le nom de Pál Turán, qui les a définis et utilisés pour la démonstration du théorème de Turán[2].

Notes et références

Chong-Yun Chao et George A Novacky Jr, « On maximally saturated graphs », Discrete Mathematics, Elsevier, vol. 41, n^o 2,‎ 1982, p. 139-143
Paul Turán, « On an extremal problem in graph theory », Matematikai és Fizikai Lapok, vol. 48,‎ 1941, p. 436–452

Voir aussi

Article connexe

Théorème d'Erdős-Stone

Lien externe

(en) Eric W. Weisstein, « Turán Graph », sur MathWorld

Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Chong-Yun Chao et George A Novacky Jr, « On maximally saturated graphs », Discrete Mathematics, Elsevier, vol. 41, n^o 2,‎ 1982, p. 139-143

[2] Paul Turán, « On an extremal problem in graph theory », Matematikai és Fizikai Lapok, vol. 48,‎ 1941, p. 436–452