Caractérisation des graphes de Laborde-Mulder et du demi-cube

Couverture
IMAG, Informatique et Mathématiques Appliquées de Grenoble, 1991 - 8 pages
0 Avis
Abstract: "The identication [sic] of antipodic vertices in the n-dimensional cube (n [> or =] 3) leads to a (0,2)-graph on 2[superscript n-1] vertices, regular of degree n and of diameter [n/2]. Such graphs are called Laborde-Mulder graphs (or LM(Q[subscript n]) for short) for n odd, and, we obtain the halfcubes for n even. In the previous paper we prove that a (0,2)-graph on 2[superscript n-1] vertices, regular of degree n has a diameter of at least [n/2]; further, the diameter is exactly [n/2] if and only if the graph is a Laborde-Mulder or a halfcube graph. Finally, we prove that the identification of vertices joined by the edges of a given matching leads to a (0,2)-graph on 2[superscript n-2] vertices, regular of degree n-1 and of diameter [(n-1)/2]."

Avis des internautes - Rédiger un commentaire

Aucun commentaire n'a été trouvé aux emplacements habituels.

Informations bibliographiques