Le diamètre de la somme cartésienne de deux graphes est la somme de leurs
diamètres.
Celui du produit fort le maximum de ces deux diamètres.
En revanche, le produit cartésien de deux graphes connexes peut ne pas être
connexe: il suffit que les graphes soient bipartis. Dans le cas orienté,
la connexité du produit demande que les index d'imprimitivité
(c'est-à-dire le p.g.c.d. des longueurs des circuits) des deux graphes soient
premiers entre eux.
Le calcul du diamètre est un peu plus aisé pour les graphes sommet-transitifs,
car il suffit de calculer les distances à partir d'un seul sommet.
9.2 Groupes engendrés par des transpositions
Le diamètre du permutoèdre sur n éléments est n(n-1)/2.
Celui du
star-graphe asocié à K1,n est 3n/2 si n est pair, 3(n-1)/2+1
si n est impair.
Pour un graphe quelconque, de diamètre d et de rayon r, le graphe de
Cayley
correspondant a un diamètre évidemment au moins égal à d et au plus
2nr.
9.3 Groupes engendrés par des involutions
Dans le même ordre d'idées, le graphe des n crêpes est le graphe
de Cayley sur n avec le générateur formé des n-1 involutions
(1,2), (1,3), (1,4)(2,3),...,(1,2k)(2,k-1)···(k,k+1),
(1,2k+1)(2,2k)···(k,k+2),...,
Celui des crêpes brûlées est le graphe de Cayley du groupe à n!2n
éléments avec un générateur formé des n involutions dans S2n
(1,2), (1,4)(2,3),..., (1,2k)···(k,k+1), ...,
(1,2n)(2,2n-1)···(n,n+1).
Leur diamètre (en fonction de n) est déjà d'une évaluation délicate, bien
qu'il se majore aisément par 2n-3 pour n³2 pour le premier et
3n-2 pour le second. On utilise le procédé suivant pour cela:
Cas des crêpes si la crêpe en position n n'est pas la crêpe n,
prendre l'involution qui amène la crêpe n en position 1, puis celle qui
la met en position n et recommencer avec les n-1 autres crêpes,
pour n³3. Le cas n£ 2 est trivial.
Cas des crêpes brûlées si la crêpe en position 2n n'est pas la crêpe (2n-1,2n),
ramener la crêpe (2n-1,2n) en position (1,2) ou (2,1)
au besoin la retourner pour la mettre en position (2,1),
puis l'envoyer en position (2n-1,2n) puis recommencer avec
les n-1 autres crêpes.
La figure 9.1 montre que la borne ci-dessus est déjà trop grande
pour n=4. Cette borne a été étudiée dans [75].
La figure 9.2 montre le cas n=2 (où la borne est juste)
et la figure 9.3 montre une statégie pour n=3,
ce qui donne le diamètre 6 au lieu de 7; quelques
arêtes inutiles sont omises.
La configuration ``bien rangée'' est à gauche dans les trois cas.
Figure 9.1 : Le graphe des crêpes (4 crêpes)
Figure 9.2 : Le graphe des crêpes brûlées(2 crêpes)
Figure 9.3 : Graphe (partiel) des crêpes brûlées(3 crêpes)
n avec le générateur formé des n-1 involutions
(1,2), (1,3), (1,4)(2,3),...,(1,2k)(2,k-1)···(k,k+1),
(1,2k+1)(2,2k)···(k,k+2),...,
