Worldlex Wiki En théorie des graphes , un graphe en roue est un graphe formé en reliant un seul sommet universel à tous les sommets d'un cycle . Un graphe en roue à n sommets peut également être défini comme le squelette 1 d'une pyramide ( n -1 )-gonale .
Certains auteurs écrivent W n pour désigner un graphe en roue à n sommets ( n ≥ 4 ) ; d'autres auteurs utilisent plutôt W n pour désigner un graphe en roue à n + 1 sommets ( n ≥ 3 ), qui est formé en reliant un seul sommet à tous les sommets d'un cycle de longueur n . La première notation est utilisée dans le reste de cet article et dans le tableau de droite.
Ensemble de bordures
{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}} serait l'ensemble d'arêtes d'un graphe de roue avec l'ensemble de sommets {1, 2, …, v} dans lequel le sommet 1 est un sommet universel .
Propriétés
Les graphes de roue sont des graphes planaires et ont un encastrement planaire unique. Plus précisément, chaque graphe de roue est un graphe de Halin . Ils sont auto-duaux : le dual planaire de tout graphe de roue est un graphe isomorphe . Tout graphe planaire maximal, autre que K 4 = W 4 , contient comme sous-graphe soit W 5 soit W 6 .
Il y a toujours un cycle hamiltonien dans le graphe de la roue et il y a des cycles dans W n (séquence A002061 dans l' OEIS ).
Pour des valeurs impaires de n , W n est un graphe parfait de nombre chromatique 3 : les sommets du cycle peuvent être de deux couleurs et le sommet central d'une troisième couleur. Pour n pair , W n a un nombre chromatique de 4 et (quand n ≥ 6) n'est pas parfait. W 7 est le seul graphe de roue qui soit un graphe de distance unitaire dans le plan euclidien.
Le polynôme chromatique du graphe de roue W n est :
En théorie des matroïdes , deux classes spéciales de matroïdes particulièrement importantes sont les matroïdes de roue et les matroïdes de tourbillon , tous deux dérivés de graphes de roue. Le matroïde de k -roue est le matroïde graphique d'une roue W k+1 , tandis que le matroïde de k -tourbillon est dérivé de la k -roue en considérant le cycle extérieur de la roue, ainsi que tous ses arbres couvrants , comme indépendants.
Français La roue W 6 a fourni un contre-exemple à une conjecture de Paul Erdős sur la théorie de Ramsey : il avait conjecturé que le graphe complet a le plus petit nombre de Ramsey parmi tous les graphes avec le même nombre chromatique, mais Faudree et McKay (1993) ont montré que W 6 a un nombre de Ramsey 17 tandis que le graphe complet avec le même nombre chromatique, K 4 , a un nombre de Ramsey 18. C'est-à-dire que pour tout graphe de 17 sommets G , soit G soit son complémentaire contient W 6 comme sous-graphe, alors que ni le graphe de Paley à 17 sommets ni son complémentaire ne contiennent une copie de K 4 .
