# Échelle de Möbius

Dans la théorie des graphes, une branche des mathématiques, l'échelle de Möbius $ML_{n}$ est un graphe cubique formé à partir du graphe cycle à $2n$ sommets en ajoutant des arêtes entre les sommets opposés du cycle.
Les graphes de cette famille sont nommés ainsi car, si l'on excepte $ML_{3}$, $ML_{n}$ possède exactement $n$ cycles à 4 sommets qui, mis ensemble par leurs sommets partagés, forment l'équivalent d'un ruban de Möbius. Les échelles de Möbius ont été nommées et étudiées pour la première fois par Richard Guy et Frank Harary en 1967.

## Propriétés

Les échelles de Möbius sont des graphes circulants.
Elles ne sont pas des graphes planaires, mais peuvent être rendues planaires en supprimant un seul sommet, ce qui en fait des graphes apex (en). Il est possible de le dessiner sur un plan avec un seul croisement et ce nombre est minimal. Il peut être plongé dans un tore ou un plan projectif sans croisements, il s'agit donc d'exemple de graphe toroïdal. De-Ming Li a exploré des plongements de ces graphes sur des surfaces d'ordre supérieur.
Les échelles de Möbius sont sommet-transitives mais ne sont pas arête-transitives (sauf $ML_{3}$) : chaque montant de l'échelle appartient à un seul cycle de 4 sommets, tandis que les barreaux de l'échelle appartiennent chacun à deux de ces cycles.
Le théorème de Brooks et le fait que le graphe soit cubique garantissent que 3 couleurs suffisent à le colorer. De fait, quand $n$ est pair, on a besoin des trois couleurs, et dans le cas contraire deux couleurs suffisent. De plus, les échelles de Möbius sont déterminées de façon unique par leurs polynômes chromatiques.
L'échelle de Möbius $ML_{4}$ possède 392 arbres couvrants. Elle et $ML_{3}$ ont le plus d'arbres couvrants parmi tous les graphes cubiques ayant le même nombre de sommets$^,$. Ce n'est toutefois pas général. En effet, le graphe cubique à 10 sommet ayant le plus d'arbres couvrants est le graphe de Petersen, qui n'est pas une échelle de Möbius.
Les polynômes de Tuttes des échelles de Möbius peuvent être calculés à l'aide d'une simple relation de récurrence.

## Mineurs du graphe

Les échelles de Möbius jouent un rôle important dans l'histoire de mineurs de graphes. Le résultat le plus ancien dans ce domaine est le théorème de 1937 de Klaus Wagner affirmant que les graphes sans mineur peut être formé en utilisant des opérations de somme de clique (en) pour combiner des graphes planaires et l'échelle de Möbius $ML_{4}$. Pour cette raison, $ML_{4}$ est appelé le graphe de Wagner.
Gubser (1996) définit un graphe presque planaire comme un graphe non planaire dans lequel tout mineur non trivial est planaire. Il montre que les graphes presque planaires 3-connexes sont des échelles de Möbius ou des membres d'un petit nombre d'autres familles et que d'autres graphes presque-planaires peuvent être formés à partir d'une suite d'opérations simples.
John Maharry a montré que presque tous les graphes qui n'ont pas un mineur cubique peuvent être déduits d'une suite d'opérations simples à partir d'échelles de Möbius.

## Applications

D. Walba et ses collègues ont synthétisé les premiers des structures moléculaires en forme d'échelle de Möbius, et depuis cette structure a été objet d'intérêt en chimie et en stéréochimie, et en particulier en relation avec la forme en échelle des molécules d'ADN. En gardant cette application à l'esprit, Erica Flapan étudie les symétries mathématiques des plongements des échelles de Möbius dans $\mathbb {R} ^{3}$.
Les échelles de Möbius ont également été utilisées pour la forme d'anneaux supraconducteurs dans des expériences consistant à étudier la structure spatiale des conducteurs dans les interactions entre électrons$^,$.
Enfin, elles ont également été utilisées en informatique, dans le cadre d'approches par optimisation linéaire en nombres entiers de problèmes de set packing et d'ordonnancement. Les échelles de möbius peuvent servir à définir les facettes du polytope qui décrit une relaxation continue du problème ; ces facettes sont appelées contraintes en échelle de Möbius$^,$$^,$$^,$$^,$.