Graphe en échelle

	Graphe en échelle
	; Les graphes en échelle , , , et .
Notation
Nombre de sommets
Nombre d'arêtes
Diamètre
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 modifier

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 modifier

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\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}$ ^[1].

Extensions cycliques modifier

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'=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^[2].

Notes et références modifier

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

↑ Ralph Grimaldi, Fibonacci and Catalan Numbers: An Introduction, John Wiley & Sons, 2012, 64 p. (ISBN 1-118-15976-4)
↑ 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 modifier

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é modifier

Graphe étoile

Liens externes modifier

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

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

[1]

[2]

Graphe en échelle
Les graphes en échelle $L_{1}$ , $L_{2}$ , $L_{3}$ , $L_{4}$ et $L_{5}$ .

Notation	$L_{n}$
Nombre de sommets	$2n$
Nombre d'arêtes	$3n-2$
Diamètre	$n$
Nombre chromatique	2
Indice chromatique	3 pour n > 2 n pour n = 1,2
Propriétés	Distance-unité Hamiltonien Planaire Biparti
modifier