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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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.