Second snark de Blanuša

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Second snark de Blanuša
image illustrative de l’article Second snark de Blanuša
Représentation du second snark de Blanuša

Nombre de sommets 18
Nombre d'arêtes 27
Distribution des degrés 3-régulier
Rayon 4
Diamètre 4
Maille 5
Automorphismes 4 (Z/2Z×Z/2Z)
Nombre chromatique 3
Indice chromatique 4
Propriétés Régulier
Snark
Cubique
Hypohamiltonien

Le second snark de Blanuša est, en théorie des graphes, un graphe 3-régulier possédant 18 sommets et 27 arêtes.

Propriétés[modifier | modifier le code]

Propriétés générales[modifier | modifier le code]

Le diamètre du second snark de Blanuša, l'excentricité maximale de ses sommets, est 4, son rayon, l'excentricité minimale de ses sommets, est 4 et sa maille, la longueur de son plus court cycle, est 5. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

Coloration[modifier | modifier le code]

Le nombre chromatique du second snark de Blanuša est 3. C'est-à-dire qu'il est possible de le colorer avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'indice chromatique du second snark de Blanuša est 4. Il existe donc une 4-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal. Le second snark de Blanuša est donc un snark, un graphe connexe, sans isthme, cubique, de maille au moins 5 et d'indice chromatique 4. De 1898 à 1946, le graphe de Petersen est le seul snark connu, jusqu'à ce que la Danilo Blanuša exhibe deux autres exemples, le premier snark de Blanuša et le second snark de Blanuša[1].

Le théorème du snark, un résultat conjecturé par W. T. Tutte et prouvé en 2001 par Robertson, Sanders, Seymour et Thomas, affirme que tout snark admet le graphe de Petersen comme mineur[2]. Le second snark de Blanuša admet donc le graphe de Petersen comme mineur.

Propriétés algébriques[modifier | modifier le code]

Le groupe d'automorphismes du second snark de Blanuša est un groupe abélien d'ordre 4 isomorphe à Z/2Z×Z/2Z, le groupe de Klein.

Le polynôme caractéristique de la matrice d'adjacence du second snark de Blanuša est : .

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) Danilo Blanuša, « Problem četiriju boja », Glasnik Mat. Fiz. Astr. Ser II, vol. 1,‎ , p. 31–42
  2. (en) Ed, Jr. Pegg, Book Review: The Colossal Book of Mathematics, vol. 49, (lire en ligne), chap. 9, p. 1084–1086.