Graphe roue

Graphe roue
Quelques exemples de graphe roue.
Notation	Wn
Nombre de sommets	n
Nombre d'arêtes	2(n − 1)
Distribution des degrés	n-1 sommets de degré 3 1 sommet de degré n-1
Diamètre	2 pour n>4 1 pour n=4
Maille	3
Nombre chromatique	3 si n est impair 4 si n est pair
Propriétés	Hamiltonien Planaire Autodual
modifier

En théorie des graphes, le graphe roue W_n est un graphe d'ordre formé en ajoutant un sommet "centre" connecté à tous les sommets du graphe cycle C_n-1^[1]. La notation W_n provient du nom anglais wheel graph mais n'est pas universelle. Certains auteurs préfèrent W_n-1, faisant référence à la longueur du cycle.

Propriétés

Propriétés générales

Pour les valeurs impaires de n, le graphe W_n est un graphe parfait. Quand n est pair et supérieur ou égal à 6, le graphe roue W_n n'est pas parfait.

Le nombre de cycles dans le graphe roue W_n est égal à n² − 3n + 3, soit la séquence A002061 de la Sloane Encyclopedia of Integer Sequences^[2] : 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, 273, 307, 343, 381, 421, 463, 507 (pour n=4, 5, 6,…). De plus le graphe roue contient toujours un cycle hamiltonien. Quel que soit n, sa maille, la longueur de son plus court cycle, est 3.

Les cycles du graphe roue W₄ (le graphe tétraédrique).

Le graphe roue est planaire. Il a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête n'en croise une autre. À partir de cette représentation, il est possible de définir son graphe dual. C'est le graphe dont les sommets correspondent aux faces du graphe roue et où deux sommets sont adjacents s'ils correspondent à deux faces adjacentes. Le dual du graphe roue W_n est W_n lui-même, faisant du graphe roue un graphe autodual. Tout graphe planaire maximal autre que le graphe complet K₄ = W₄, contient comme sous-graphe ou W₅ ou W₆.

W₇ est le seul graphe roue à être distance-unité^[3].

Le graphe roue W₆ est un contre-exemple à une conjecture de Paul Erdős sur la théorie de Ramsey. Erdős avait conjecturé que le graphe complet avait le plus petit nombre de Ramsey parmi tous les graphes avec le même nombre chromatique, mais Faudree et McKay montrèrent en 1993 que W₆ a un nombre de Ramsey égal à 17 alors que le graphe complet avec le même nombre chromatique, K₄, a un nombre de Ramsey égal à 18^[4]. En effet, pour tout graphe G d'ordre 17, G ou son complément contient un sous-graphe isomorphe à W₆, alors que ni le graphe de Paley d'ordre 17 ni son complément ne contiennent un sous-graphe isomorphe à K₄.

Coloriage

Pour les valeurs impaires de n, le graphe W_n a un nombre chromatique de 3 : les sommets du cycle C_n-1 peuvent être colorées avec deux couleurs et le centre se voit attribuer la troisième couleur. Pour n pair le graphe à un nombre chromatique égal à 4 : les sommets du cycle C_n-1 nécessitent trois couleurs et le centre se voit attribuer la quatrième couleur.

Il est possible de compter les colorations distinctes d'un graphe. Cela donne une fonction dépendant du nombre de couleurs autorisé. Cette fonction est polynomiale et est qualifiée de polynôme chromatique du graphe. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs à au nombre chromatique du graphe et est de degrés n. Il est égal à :

Références

• Portail de l'informatique théorique