Complémentaire d'un graphe fortement régulier — Les-mathematiques.net The most powerful custom community solution in the world

Complémentaire d'un graphe fortement régulier

Bonjour
Démontrer que le complémentaire d’un graphe fortement régulier de paramètres $(n,k,v,u)$ est fortement régulier de paramètres $(n, n-k-1, n-2k+u-2, n-2k+v)$.

Voici la question sur laquelle je bloque. Je ne sais même pas par où commencer pour démontrer cela. Si quelqu'un avait une piste, je prends.
Merci d'avance.

Réponses

  • D'abord, le graphe complémentaire a $n$ sommets.
    Ensuite, vu que chaque sommet est adjacent à $k$ sommets dans le graphe, il y a exactement $n-k-1$ sommets non reliés ; autrement dit, chaque sommet est relié à $n-k-1$ sommets du graphe complémentaire.
    Soient deux sommets $i$ et $j$ non adjacents dans le graphe, i.e. adjacents dans le graphe complémentaire. Comptons les sommets adjacents à tous les deux dans le graphe complémentaire : ce sont les sommes qui ne sont adjacents à aucun des deux. Parmi les $n-2$ sommets autres que $i$ et $j$, ceux qui sont adjacents à au moins un des deux sont au nombre de $2k-u$ : il y a en effet $k$ sommets adjacents à $i$ et $k$ adjacents à $j$, soit $2k$ en tout, parmi lesquels on a compté deux fois les $u$ sommets adjacents à $i$ et $j$. Au bilan : $n-2-(2k-u)$ sommets qui ne sont adjacents ni à $i$, ni à $j$ dans le graphe initial.
    Le dernier calcul doit être du même tabac.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!