Graphe en échelle

Modèle:Infobox Graphe Un graphe en échelle (en Modèle:Lang-en) 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,\dots ,v_{2n}\}$

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

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

Propriétés

2-coloration du graphe en échelle $L_8$.

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\ge 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

Deux vues d'un graphe en échelle de Möbius.

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^{\prime }=E\cup \{\{v_1,v_{2n-1}\},\{v_2,v_{2n}\}\}$ ,

et on obtient un graphe en échelle cyclique (Modèle:Lang-en), noté $C{L}_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\ge 2$. Les graphes en échelle cycliques sont les graphes polyédriques de prismes et sont également appelés graphes prismatiques ou graphes de prisme (Modèle:Lang-en).

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

$E^{\prime }=E\cup \{\{v_1,v_{2n}\},\{v_2,v_{2n-1}\}\}$ ,

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

Bibliographie

• Modèle:Ouvrage.

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.

Article lié

• Graphe étoile

Liens externes

• Modèle:MathWorld