Reconnaissance de certains graphes de type hypercubes

Abstract

L’ensemble des voisins communs à une distance donnée i d’un sommet u, noté Ni(u), représente une propriété importante dans la classe des (0, 2)-graphes ( qui admet l’hypercube comme graphe maximum), où chaque paire de sommets a excte- ment deux voisins commun à distance 1 ou aucun.À travers ce manuscrit et au chapitre 3 on donne une reconnaissance des {2, 2}- graphes où chaque paire de sommets a exactement 2 voisins communs à distance 2 ou aucun.Au chapitre 4 on essaye également de donner une reconnaissance des graphes [4, 1, 8]- cycle réguliers où chaque chaîne de longueur 4 appartient à exactement un cycle de longueur 8 ou aucun.