Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe roue
Résumé
En théorie des graphes, le graphe roue Wn est un graphe d'ordre formé en ajoutant un sommet « centre » connecté à tous les sommets du graphe cycle Cn-1. La notation Wn provient du nom anglais wheel graph mais n'est pas universelle. Certains auteurs préfèrent Wn-1, faisant référence à la longueur du cycle.
Pour les valeurs impaires de n, le graphe Wn est un graphe parfait. Quand n est pair et supérieur ou égal à 6, le graphe roue Wn n'est pas parfait.
Le nombre de cycles dans le graphe roue Wn est égal à () : 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.
thumb|upright=2.0|center|Les cycles du graphe roue W4 (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 Wn est Wn lui-même, faisant du graphe roue un graphe autodual. Tout graphe planaire maximal autre que le graphe complet K4 = W4, contient comme sous-graphe ou W5 ou W6.
W7 est le seul graphe roue à être distance-unité.
Le graphe roue W6 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 W6 a un nombre de Ramsey égal à 17 alors que le graphe complet avec le même nombre chromatique, K4, a un nombre de Ramsey égal à 18. En effet, pour tout graphe G d'ordre 17, G ou son complément contient un sous-graphe isomorphe à W6, alors que ni le graphe de Paley d'ordre 17 ni son complément ne contiennent un sous-graphe isomorphe à K4.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (1)