Snark de Watkins

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Snark de Watkins
Image illustrative de l'article Snark de Watkins
Représentation du snark de Watkins

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

Le snark de Watkins est, en théorie des graphes, un graphe 3-régulier possédant 50 sommets et 75 arêtes.

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

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

Le diamètre du snark de Watkins, l'excentricité maximale de ses sommets, est 7, son rayon, l'excentricité minimale de ses sommets, est 7 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 snark de Watkins 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 mais ce nombre est minimal. Il n'existe pas de 2-coloration valide du graphe.

L'indice chromatique du snark de Watkins 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.

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

Le groupe d'automorphismes du snark de Watkins est un groupe abélien d'ordre 5 isomorphe au groupe cyclique Z/5Z.

Le polynôme caractéristique de la matrice d'adjacence du snark de Watkins est : (x-3) (x-1)^9 (x+2)^4 (x^{18}+2 x^{17}-27 x^{16}-56 x^{15}+290 x^{14}+623 x^{13}-1589 x^{12}-3541 x^{11}+4752 x^{10}+11035 x^9-7705 x^8-18755 x^7+6375 x^6+16165 x^5-2460 x^4-5829 x^3+532 x^2+558 x+29)^2.

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]