Graphe en échelle
# Graphe en échelle

Un graphe en échelle (en anglais : ladder graph) est, en théorie des graphes, une famille de graphes qui ont la structure d'une échelle. Un graphe en échelle se compose de deux graphes linéaires de même longueur (les montants), et deux nœuds correspondants sont reliés par une arête (les barreaux). Chaque graphe en échelle est le produit cartésien de deux graphes linéaires, dont l'un a exactement une arête ; c'est donc un graphe grille particulier.

## Définition

Un graphe en échelle $L_{n}$ est un graphe non orienté $(V,E)$ composé de $2n$ nœuds :

    $V=\{v_{1},\ldots ,v_{2n}\}$

et de $3n-2$ arêtes :

    $E=\{\{v_{i},v_{i+1}\}\mid i=1,3,\ldots ,2n-1\}\cup \{\{v_{i},v_{i+2}\}\mid i=1,2,\ldots ,2n-2\}$ .

## Propriétés

Un graphe en échelle $L_{n}$ est le produit cartésien

    $L_{n}=P_{2}\times P_{n}$

des deux graphes linéaires $P_{2}$ et $P_{n}$ et est ainsi le graphe grille particulier $G_{2,n}$ .

D'autres propriétés sont :

* Les graphes en échelle sont connexes, planaires et bipartis . Pour $n\geq 2$, ils sont également cycliques et hamiltoniens.
* À l'exception des quatre nœuds d'angle de degré deux, les nœuds d'un graphe en échelle sont de degré 3.
* Le diamètre et la taille maximale d'un ensemble stable du graphe en échelle $L_{n}$ sont tous deux égaux à $n$.
* Le nombre chromatique du graphe en échelle $L_{n}$ est 2 et son polynôme chromatique est $(\lambda -1)\lambda (\lambda ^{2}-3\lambda +3)^{n-1}$.
* Le nombre de couplages parfaits du graphe en échelle $L_{n}$ est égal au nombre de Fibonacci $f_{n+1}$.

## Extensions cycliques

Lorsque l'on relie, dans un graphe en échelle, le premier et l'avant-dernier ainsi que le deuxième et le dernier nœud sont reliés l'un à l'autre par une arête supplémentaire, on obtient l'ensemble d'arêtes

    $E'=E\cup \{\{v_{1},v_{2n-1}\},\{v_{2},v_{2n}\}\}$ ,

et on obtient un graphe en échelle cyclique (anglais : circular ladder graph), noté $CL_{n}$ . Un graphe en échelle cyclique est le produit cartésien $P_{2}\times C_{n}$ d'un graphe linéaire avec un graphe cycle $C_{n}$ ; il est donc 3-régulier pour $n\geq 2$. Les graphes en échelle cycliques sont les graphes polyédriques de prismes et sont également appelés graphes prismatiques ou graphes de prisme (anglais : prism graphs).

Si les quatre nœuds sont en revanche connectés en croix, on forme l'ensemble d'arêtes

    $E'=E\cup \{\{v_{1},v_{2n}\},\{v_{2},v_{2n-1}\}\}$ ,

et on obtient un graphe appelé graphe en échelle de Möbius (en anglais : Möbius ladder graph), noté $ML_{n}$ ; il rappelle la bande de Möbius et est également 3-régulier. Les graphes en échelle de Möbius pour $n\geq 3$ ne sont plus planaires ; ils ont des propriétés intéressantes en théorie des graphes.

