Groupe d’études et de recherche en analyse des décisions

\(k\)-domination et \(k\)-indépendance dans les graphes

Odile Favaron Laboratoire de recherche en informatique, Université Paris Sud, France

En 1984, Fink et Jacobson ont introduit la généralisation suivante des concepts de domination et d'indépendance. Un ensemble \(S\) de sommets d'un graphe \(G=(V,E)\) est \(k\)-dominant si tout sommet de \(V\setminus S\) a au moins \(k\) voisins dans \(S\) et \(k\)-indépendant si tout sommet de \(S\) a moins de \(k\) voisins dans \(S\). Les paramètres \(\gamma_k(G)\) et \(\Gamma_k(G)\) sont respectivement les cardinaux minimum et maximum d'un k-dominant minimal de \(G\). De même, \(i_k(G)\) et \(\beta_k(G)\) sont respectivement les cardinaux minimum et maximum d'un \(k\)-indépendant maximal de \(G\). À la suite de ces définitions et des deux conjectures qui les accompagnaient, un certain nombre de travaux ont été effectués par différents auteurs. Nous donnons un aperçu des principaux résultats qui portent essentiellement sur la comparaison entre ces paramètres, sur la détermination de différentes bornes et sur la rapidité de croissance de la suite \(\gamma_k\).