Graphique de Moore

En théorie des graphes , un graphe de Moore est un graphe régulier dont la circonférence (la longueur du cycle le plus court ) est supérieure à deux fois son diamètre (la distance entre les deux sommets les plus éloignés ). Si le degré d'un tel graphe est d et son diamètre est k , sa circonférence doit être égale à 2 k + 1. Ceci est vrai, pour un graphe de degré d et de diamètre k , si et seulement si son nombre de sommets est égal à

une limite supérieure sur le plus grand nombre possible de sommets dans tout graphe avec ce degré et ce diamètre. Par conséquent, ces graphes résolvent le problème du degré et du diamètre pour leurs paramètres.

Une autre définition équivalente d'un graphe de Moore G est qu'il a une circonférence g = 2 k + 1 et précisément ⁠n/g⁠ ( m – n + 1) cycles de longueur g , où n et m sont respectivement les nombres de sommets et d'arêtes de G . Ils sont en fait extrémaux par rapport au nombre de cycles dont la longueur est la circonférence du graphe.

Les graphes de Moore ont été nommés par Hoffman et Singleton (1960) d'après Edward F. Moore , qui a posé la question de la description et de la classification de ces graphes.

En plus d'avoir le nombre maximal possible de sommets pour une combinaison donnée de degré et de diamètre, les graphes de Moore ont le nombre minimal possible de sommets pour un graphe régulier avec un degré et une circonférence donnés. Autrement dit, tout graphe de Moore est une cage . La formule du nombre de sommets dans un graphe de Moore peut être généralisée pour permettre une définition de graphes de Moore avec une circonférence paire ainsi qu'une circonférence impaire, et encore une fois ces graphes sont des cages.

Soit G un graphe quelconque de degré maximal d et de diamètre k , et considérons l'arbre formé par la recherche en largeur à partir de n'importe quel sommet v . Cet arbre a 1 sommet au niveau 0 ( v lui-même), et au plus d sommets au niveau 1 (les voisins de v ). Au niveau suivant, il y a au plus d ( d − 1) sommets : chaque voisin de v utilise une de ses adjacences pour se connecter à v et peut donc avoir au plus d − 1 voisins au niveau 2. En général, un argument similaire montre qu'à tout niveau 1 ≤ i ≤ k , il peut y avoir au plus d ( d − 1) ^{i −1} sommets. Ainsi, le nombre total de sommets peut être au plus de

Hoffman et Singleton (1960) ont initialement défini un graphe de Moore comme un graphe pour lequel cette limite sur le nombre de sommets est respectée exactement. Par conséquent, tout graphe de Moore possède le nombre maximal de sommets possible parmi tous les graphes de degré maximal d et de diamètre maximal k .

Plus tard, Singleton (1968) a montré que les graphes de Moore peuvent être définis de manière équivalente comme ayant un diamètre k et une circonférence 2 k + 1 ; ces deux exigences se combinent pour forcer le graphe à être d -régulier pour un certain d et pour satisfaire la formule de comptage de sommets.

Français Au lieu de limiter supérieurement le nombre de sommets d'un graphe en fonction de son degré maximum et de son diamètre, nous pouvons calculer via des méthodes similaires une limite inférieure sur le nombre de sommets en fonction de son degré minimum et de sa circonférence. Supposons que G ait un degré minimum d et une circonférence de 2 k + 1 . Choisissez arbitrairement un sommet de départ v , et comme précédemment considérez l'arbre de recherche en largeur d'abord enraciné à v . Cet arbre doit avoir un sommet au niveau 0 ( v lui-même), et au moins d sommets au niveau 1. Au niveau 2 (pour k > 1 ), il doit y avoir au moins d ( d − 1) sommets, car chaque sommet au niveau 1 a au moins d − 1 adjacences restantes à remplir, et aucun sommet au niveau 1 ne peut être adjacent l'un à l'autre ou à un sommet partagé au niveau 2 car cela créerait un cycle plus court que la circonférence supposée. En général, un argument similaire montre qu'à tout niveau 1 ≤ i ≤ k , il doit y avoir au moins d ( d − 1) ⁱ sommets. Ainsi, le nombre total de sommets doit être au moins égal à

Dans un graphe de Moore, cette limite sur le nombre de sommets est respectée exactement. Chaque graphe de Moore a une circonférence exactement égale à 2 k + 1 : il n'a pas assez de sommets pour avoir une circonférence plus élevée, et un cycle plus court entraînerait un nombre trop faible de sommets dans les k premiers niveaux d'un arbre de recherche en largeur. Par conséquent, tout graphe de Moore a le nombre minimum de sommets possible parmi tous les graphes de degré minimum d et de circonférence 2 k + 1 : c'est une cage.

Pour une circonférence paire de 2 k , on peut de la même manière former un arbre de recherche en largeur à partir du milieu d'une seule arête. La limite résultante sur le nombre minimal de sommets dans un graphe de cette circonférence avec un degré minimal d est

(Le côté droit de la formule compte plutôt le nombre de sommets dans un arbre de recherche en largeur à partir d'un seul sommet, en tenant compte de la possibilité qu'un sommet du dernier niveau de l'arbre puisse être adjacent à d sommets du niveau précédent.) Ainsi, les graphes de Moore sont parfois définis comme incluant les graphes qui respectent exactement cette limite. Là encore, tout graphe de ce type doit être une cage.

Le théorème de Hoffman-Singleton stipule que tout graphe de Moore de circonférence 5 doit avoir un degré 2, 3, 7 ou 57. Les graphes de Moore sont :

• Les graphes complets K _n sur n > 2 nœuds (diamètre 1, circonférence 3, degré n − 1 , ordre n )
• Les cycles impairs C _{2 n + 1} (diamètre n , circonférence 2 n + 1 , degré 2, ordre 2 n + 1 )
• Le graphe de Petersen (diamètre 2, circonférence 5, degré 3, ordre 10)
• Le graphe de Hoffman–Singleton (diamètre 2, circonférence 5, degré 7, ordre 50)
• Un graphe hypothétique (ou plusieurs) de diamètre 2, de circonférence 5, de degré 57 et d'ordre 3250 ; l'existence d'un tel graphe est inconnue et constitue l'un des problèmes ouverts les plus célèbres de la théorie des graphes.

Bien que tous les graphes de Moore connus soient des graphes vertex-transitifs , l'inconnu (s'il existe) ne peut pas être vertex-transitif, car son groupe d'automorphismes peut avoir un ordre au plus égal à 375, inférieur à son nombre de sommets.

Si l'on utilise la définition généralisée des graphes de Moore qui autorise les graphes de circonférence paire, les graphes de Moore de circonférence paire correspondent aux graphes d'incidence de polygones généralisés (éventuellement dégénérés) . Quelques exemples sont les cycles pairs C _{2 n} , les graphes bipartis complets K _{n , n} de circonférence quatre, le graphe de Heawood de degré 3 et de circonférence 6, et le graphe de Tutte–Coxeter de degré 3 et de circonférence 8. Plus généralement, on sait que, outre les graphes listés ci-dessus, tous les graphes de Moore doivent avoir une circonférence de 5, 6, 8 ou 12. Le cas de circonférence paire découle également du théorème de Feit-Higman sur les valeurs possibles de n pour un n -gone généralisé .