Graphe en échelle

Graphe en échelle
Les graphes en échelle ${\displaystyle L_{1}}$, ${\displaystyle L_{2}}$, ${\displaystyle L_{3}}$, ${\displaystyle L_{4}}$ et ${\displaystyle L_{5}}$.
Notation	${\displaystyle L_{n}}$
Nombre de sommets	${\displaystyle 2n}$
Nombre d'arêtes	${\displaystyle 3n-2}$
Diamètre	${\displaystyle n}$
Nombre chromatique	2
Indice chromatique	3 pour n > 2 n pour n = 1,2
Propriétés	Distance-unité Hamiltonien Planaire Biparti
modifier

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

Propriétés

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].

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

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

Notes et références

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

1. Ralph Grimaldi, Fibonacci and Catalan Numbers: An Introduction, John Wiley & Sons, 2012, 64 p. (ISBN 1-118-15976-4)
2. Jonathan L. Gross, Combinatorial Methods With Computer Applications, CRC Press, coll. « Discrete Mathematics and its Applications » (n^o 54), 2008 (ISBN 1-58488-743-5), p. 376–377.

Bibliographie

• 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).

Article lié

• Graphe étoile

Liens externes

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