Snark fleur
From Wikipedia, the free encyclopedia
NotationJn avec n impair
Nombre de sommets4n
Nombre d'arêtes6n
Maille3 pour n = 3
5 pour n = 5
6 pour n ≥ 7
5 pour n = 5
6 pour n ≥ 7
| Snark fleur | |
 Les snarks fleurs J3, J5 et J7 | |
| Notation | Jn avec n impair |
|---|---|
| Nombre de sommets | 4n |
| Nombre d'arêtes | 6n |
| Maille | 3 pour n = 3 5 pour n = 5 6 pour n ≥ 7 |
| Nombre chromatique | 3 |
| Indice chromatique | 4 |
| Propriétés | Snark |
modifier  |
|
En mathématiques, et plus particulièrement en théorie des graphes, les snarks fleurs forment une famille infinie de snarks introduite par Rufus Isaacs en 1975[1].
Étant un snark, un snark fleur est un graphe cubique connexe et sans isthme d'indice chromatique égal à 4. Il est non-planaire et non-hamiltonien.
Le snark fleur Jn peut être construit ainsi :
- Construire n copies du graphe étoile à 4 sommets. On note le sommet central de chaque étoile Ai et les sommets périphériques Bi, Ci et Di. On obtient un graphe non connexe à 4n sommets et 3n arêtes.
- Construire le cycle à n sommets (B1 B2… Bn) (au centre sur les figures). Cela ajoute n arêtes.
- Enfin construire le cycle à 2n sommets (C1C2… CnD1D2… Dn) (à l'extérieur sur les figures, les arêtes CnD1 et DnC1 sont en bas). Cela ajoute 2n arêtes.
Par construction, le graphe obtenu Jn est un graphe cubique à 4n sommets et 6n arêtes. Pour être un snark fleur, n doit être impair.
