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

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