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.
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.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 2
2 Invités