Accueil🇫🇷Chercher

Graphe d'amitié

Dans le domaine mathématique de la théorie des graphes, le graphe d'amitié (ou graphe moulin hollandais ou n-éventail) Fn est un graphe planaire non orienté avec 2n+1 sommets et 3n arêtes[1].

Graphe d'amitié
Image illustrative de l’article Graphe d'amitié
Graphe d'amitié F8

Notation Fn
Nombre de sommets 2n+1
Nombre d'arêtes 3n
Rayon 1
Diamètre 2
Maille 3
Nombre chromatique 3
Indice chromatique 2n
Propriétés distance unitaire
planaire
eulérien
facteur critique
localement linéaire
Les graphes d'amitié F2, F3 et F4.

Construction

Le graphe d'amitié Fn peut être construit en joignant n copies du graphe cycle C3 avec un sommet commun[2].

Par construction, le graphe d'amitié Fn est isomorphe au graphe moulin Wd(3, n). C'est un graphe distance unitaire avec maille 3, diamètre 2 et rayon 1. Le graphe F2 est isomorphe au graphe papillon.

Théorème de l'amitié

Le théorème de l'amitié de Paul Erdős, Alfréd Rényi et Vera T. Sós de 1966[3] affirme que les graphes finis avec la propriété que deux sommets quelconques ont exactement un voisin en commun sont exactement les graphes d'amitié.

De manière informelle, le théorème dit que si, dans un groupe de personnes, chaque paire de personnes a exactement un ami en commun, alors il doit y avoir une personne qui est l'amie de toutes les autres.

Pour les graphes infinis, ce théorème n'est plus valable : il peut exister de nombreux graphes différents de même cardinalité et qui ont cette propriété[4].

Une preuve combinatoire du théorème d'amitié a été donnée par Mertzios et Unger[5]. Une autre preuve a été donnée par Craig Huneke[6]. Une preuve formalisée dans Metamath été donnée par Alexander van der Vekens en sur la liste de diffusion Metamath[7].

Étiquetage et coloration

Le graphe de l'amitié a le nombre chromatique 3 et l'indice chromatique 2n. Son polynôme chromatique peut être déduit du polynôme chromatique du graphe cyclique C3 ; il est égal à .

Le graphe d'amitié Fn est gracieux aux arêtes si et seulement si n est impair. Il est gracieux si et seulement si n ≡ 0 (mod 4) ou n ≡ 1 (mod 4)[8] - [9].

Chaque graphe d'amitié est un graphe à facteur critique (en).

Théorie extrémales des graphes

Selon la théorie des graphes extrémaux, tout graphe qui a suffisamment d'arêtes (par rapport à son nombre de sommets) doit contenir un -éventail en sous-graphe. Plus précisément, c'est le cas d'un graphe à sommets si le nombre d'arêtes est

où si est impair, et si est pair. Ces bornes généralisent le théorème de Turán sur le nombre d'arêtes dans un graphe sans triangle, et ce sont les meilleures bornes possibles pour ce problème, en ce sens que pour tout nombre d'arêtes plus petit, il existe des graphes qui ne contiennent pas de -éventail[10].

Articles connexes

Références

  1. (en) Eric W. Weisstein, « Dutch Windmill Graph », sur MathWorld.
  2. Joseph A. Gallian, « A dynamic survey of graph labeling », Electronic Journal of Combinatorics,‎ , DS6 (DOI 10.37236/27 Accès libre).
  3. Paul Erdős, Alfréd Rényi et Vera T. Sós, « On a problem of graph theory », Studia Sci. Math. Hungar., vol. 1,‎ , p. 215–235 (lire en ligne).
  4. Václav Chvátal, Anton Kotzig, Ivo G. Rosenberg et Roy O. Davies, « There are friendship graphs of cardinal », Canadian Mathematical Bulletin, vol. 19, no 4,‎ , p. 431–433 (DOI 10.4153/cmb-1976-064-1 Accès libre).
  5. George Mertzios et Walter Unger, « The friendship problem on graphs », Relations, Orders and Graphs: Interaction with Computer Science,‎ (lire en ligne).
  6. Craig Huneke, « The Friendship Theorem », The American Mathematical Monthly, vol. 109, no 2,‎ , p. 192–194 (DOI 10.2307/2695332, JSTOR 2695332).
  7. « Metamath », .
  8. J.-C. Bermond, A. E. Brouwer et A. Germa, « Systèmes de triplets et différences associées », dans Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976), CNRS, Paris, coll. « Colloq. Intern. du CNRS » (no 260), (MR 539936), p. 35–38.
  9. J.-C. Bermond, A. Kotzig et J. Turgeon, « On a combinatorial problem of antennas in radioastronomy », dans Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, North-Holland, Amsterdam-New York, coll. « Colloq. Math. Soc. János Bolyai » (no 18), (MR 519261), p. 135–149.
  10. P. Erdős, Z. Füredi, R. J. Gould et D. S. Gunderson, « Extremal graphs for intersecting triangles », Journal of Combinatorial Theory Series B, vol. 64, no 1,‎ , p. 89–100 (DOI 10.1006/jctb.1995.1026 Accès libre, MR 1328293, lire en ligne).
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.