k-domination et k-indépendance dans les graphes (Odile Favaron - LRI)

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 \ 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 γ_k(G) et β_k(G) sont respectivement les cardinaux d'un k-dominant minimum et d'un k-indépendant maximum de G. A la suite de ces définitions et des deux conjectures qui les accompagnaient, un certain nombre de travaux ont été effectués. Nous donnons un apercu 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 γ_k.