Accueil🇫🇷Chercher

Étiquetage gracieux

En théorie des graphes, un étiquetage gracieux d'un graphe non orienté à m arêtes est un étiquetage de ses sommets par des entiers naturels distincts pris dans l'ensemble {0,...,m} qui a la propriété que les valeurs absolues des différences des étiquettes des extrémités des arêtes sont toutes distinctes et égales à 1,...,m ; elles identifient ainsi de manière unique les arêtes. Un graphe qui admet un étiquetage gracieux est un graphe gracieux[1] - [2].

Étiquetage gracieux. Les sommets sont étiquetés en noir, les arêtes en rouge.
Étiquetage gracieux d'une chaîne de 5 sommets.

Le terme « étiquetage gracieux » (en anglais « graceful labeling ») apparaît dans un article de Solomon W. Golomb[3] - [4] Le concept figure, sous le nom de « β-labeling » dans un article d'Alexander Rosa sur l’étiquetage de graphes[5].

Conjecture des arbres gracieux

Une des conjectures non résolues en théorie des graphes est la conjecture des arbres gracieux ou conjecture de Ringel-Kotzig, nommée ainsi d'après Gerhard Ringel and Anton Kotzig. Elle affirme :

Conjecture de Ringel-Kotzig — Tous les arbres sont gracieux.

La conjecture de Ringel-Kotzig est aussi connue sous le terme de « conjecture de l’étiquetage gracieux »[6]. Une version plus faible est la

Conjecture de Ringel — Le graphe complet peut être décomposé en copies de tout arbre à arêtes.

Cette conjecture de Ringel a été démontrée pour des grandes valeurs de dans un article posté le par Richard Montgomery, Alexey Pokrovskiy et Benny Sudakov sur Arxiv[7]. Le résultat a fait l'objet d'un article dans Quanta Magazine[8] et dans Pour la Science[9]

Résultats partiels

De nombreux résultats partiels — positifs ou négatifs — concernent des classes particulières de graphes. Un catalogue est maintenu par Joseph A. Gallian[10] :

Notes et références

  1. (en) Eric W. Weisstein, « Graceful graph », sur MathWorld
  2. Virginia Vassilevska, « Coding and Graceful Labeling of trees », SURF 2001 PostScript
  3. Solomon W. Golomb, « The Largest Graceful Subgraph of the Complete Graph », Amer. Math. Monthly, vol. 81,‎ , p. 499-501.
  4. Martin Gardner, Wheels, Life, and Other Mathematical Amusements, New York, W. H. Freeman, , Ch. 15 : « Golomb's Graceful Graphs » p. 152-165.
  5. A. Rosa, « On certain valuations of the vertices of a graph », dans Theory of Graphs (Internat. Sympos., Rome, 1966), New York, Gordon and Breach, (MR 0223271), p. 349-355.
  6. C. Huang, Anton Kotzig et Alexander Rosa, « Further results on tree labellings », Utilitas Mathematica, vol. 21,‎ , p. 31-48 (MR 668845).
  7. « A proof of Ringel's Conjecture »,
  8. Kevin Hartnett, « Rainbow Proof Shows Graphs Have Uniform Parts », sur https://www.quantamagazine.org, Quanta Magazine, (consulté le ).
  9. « La conjecture de Ringel démontrée grâce à des coloriages de graphes », .
  10. Joseph A. Joseph A. Gallian, « A dynamic survey of graph labeling », Electronic Journal of Combinatorics,‎ 1998-2016, Dynamic Survey #DS6: Dec 23, 2016 (MR = 1668059, lire en ligne).
  11. R. E. L. Aldred et Brendan D. McKay, « Graceful and harmonious labellings of trees », Bulletin of the Institute of Combinatorics and its Applications, vol. 23,‎ , p. 69-72 (MR 1621760).
  12. Michael P. Horton, Graceful Trees : Statistics and Algorithms, Université de Tasmanie, (lire en ligne).
  13. Wenjie Fang, « A Computational Approach to the Graceful Tree Conjecture », arxiv,‎ (arXiv 1003.3045).
  14. Anton Kotzig, « Decompositions of complete graphs into isomorphic cubes », Journal of Combinatorial Theory, Series B, vol. 31, no 3,‎ , p. 292-296 (DOI 10.1016/0095-8956(81)90031-9, MR 638285).

Bibliographie

  • Shalom Eliahou, « Le sudoku arboricole », Images des mathématiques : La recherche mathématique en mots et en images, CNRS, (consulté le ).
  • « Tous les arbres sont-ils gracieux ? », k a f e m a t h 2016-2017, (consulté le ).
  • Vasanti N. Bhat-Nayak et Ujwala N. Deshmukh, « Gracefulness of and », J. Ramanujan Math. Soc., vol. 11, no 2,‎ , p. 187-190 (zbMATH 0867.05057).
  • Vasanti N. Bhat-Nayak et A. Selvam, « Gracefulness of -cone », Ars Combin., vol. 66,‎ , p. 283–298 (MR 1961491).
  • (en) Eric W. Weisstein, « Graceful graph », sur MathWorld
  • Ping Zhang, A Kaleidoscopic view of graph colorings, Springer, coll. « SpringerBriefs in Mathematics », , 157 p. (ISBN 978-3-319-30518-9, lire en ligne)

Articles liés

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.