Graphe en échelle

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

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

et de ${\displaystyle 3n-2}$ arêtes :

${\displaystyle 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\}}$ .

2-coloration du graphe en échelle ${\displaystyle L_{8}}$.

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

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

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

D'autres propriétés sont :

• Les graphes en échelle sont connexes, planaires et bipartis . Pour ${\displaystyle 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 ${\displaystyle L_{n}}$ sont tous deux égaux à ${\displaystyle n}$.
• Le nombre chromatique du graphe en échelle ${\displaystyle L_{n}}$ est 2 et son polynôme chromatique est ${\displaystyle (\lambda -1)\lambda (\lambda ^{2}-3\lambda +3)^{n-1}}$.
• Le nombre de couplages parfaits du graphe en échelle ${\displaystyle L_{n}}$ est égal au nombre de Fibonacci ${\displaystyle f_{n+1}}$[1].

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

${\displaystyle 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é ${\displaystyle CL_{n}}$ . Un graphe en échelle cyclique est le produit cartésien ${\displaystyle P_{2}\times C_{n}}$ d'un graphe linéaire avec un graphe cycle ${\displaystyle C_{n}}$ ; il est donc 3-régulier pour ${\displaystyle 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

${\displaystyle 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é ${\displaystyle ML_{n}}$ ; il rappelle la bande de Möbius et est également 3-régulier. Les graphes en échelle de Möbius pour ${\displaystyle n\geq 3}$ ne sont plus planaires ; ils ont des propriétés intéressantes en théorie des graphes[2].

• (de) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en allemand intitulé « Leitergraph » (voir la liste des auteurs).

• W. W. R. Ball et H. S. M. Coxeter, Mathematical Recreations and Essays, New York, Dover, 1987, 13^e éd..

• H. Hosoya et F. Harary, « On the Matching Properties of Three Fence Graphs », J. Math. Chem., vol. 12,‎ 1993, p. 211-218.
• M. Maheo, « Strongly Graceful Graphs », Disc. Math., vol. 29,‎ 1980, p. 39-46.
• M. Noy et A. Ribó, « Recursively Constructible Families of Graphs », Adv. Appl. Math., vol. 32,‎ 2004, p. 350-363.
• Yichao Chen, Jonathan L. Gross et Toufik Mansour, « Total Embedding Distributions of Circular Ladders », Journal of Graph Theory, vol. 74, n^o 1,‎ septembre 2013, p. 32–57 (DOI 10.1002/jgt.21690, CiteSeer^x 10.1.1.297.2183).

• Graphe étoile

• (en) Eric W. Weisstein, « Ladder Graph », sur MathWorld

• Portail des mathématiques
• Portail de l'informatique théorique