É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]Modèle:,[2].
Le terme « étiquetage gracieux » (en anglais Modèle:Citation étrangère) apparaît dans un article de Solomon W. Golomb[3]Modèle:,[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 : Modèle:Théorème La conjecture de Ringel-Kotzig est aussi connue sous le terme de « conjecture de l’étiquetage gracieux »[6]. Une version plus faible est la Modèle:Théorème Cette conjecture de Ringel a été démontrée pour des grandes valeurs de dans un article posté le Modèle:Date- 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] :
- Un graphe eulérien avec m arêtes n'est pas gracieux si m ≡ 1 (mod 4) ou m ≡ 2 (mod 4)[5].
- Un cycle Cn à n sommets est gracieux si et seulement si n ≡ 0 (mod 4) ou n ≡ 3 (mod 4)[5].
- Toutes les chaînes et tous les graphes chenilles sont gracieux.
- Tout graphe biparti complet est gracieux[1].
- Les arbres à au plus 27 sommets sont gracieux[10]Modèle:,[11]. Ce résultat est étendu en 2003 aux arbres à 29 sommets par Michael Horton dans sa thèse de bachelor[12]. Une autre extension, à 35 sommets, est annoncée en 2010 par Wenjie Fang[13].
- Tout graphe roue, tout graphe grille est gracieux[10].
- Tout hypercube est gracieux[14].
- Les graphes simples avec au plus quatre sommets sont gracieux. Les seuls graphes à 5 sommets qui ne sont pas gracieux sont le 5-cycle (le pentagone); le graphe complet K5; et le graphe graphe papillon[1].
Notes et références
Modèle:Traduction/Référence Modèle:Références
Bibliographie
Articles liés
- ↑ 1,0 1,1 et 1,2 Modèle:MathWorld
- ↑ Virginia Vassilevska, « Coding and Graceful Labeling of trees », SURF 2001 PostScript
- ↑ Modèle:Article.
- ↑ Modèle:Ouvrage.
- ↑ 5,0 5,1 et 5,2 Modèle:Chapitre.
- ↑ Modèle:Article.
- ↑ Modèle:Lien web.
- ↑ Modèle:Lien web.
- ↑ Modèle:Lien web.
- ↑ 10,0 10,1 et 10,2 Modèle:Article.
- ↑ Modèle:Article.
- ↑ Modèle:Ouvrage.
- ↑ Modèle:Article.
- ↑ Modèle:Article.