La K-domination et la K-indépendance dans les graphes

Abstract

Soit G = (V; E) un graphe simple et k un entier positif. Un sous ensemble de sommets D dans le graphe G est dit k-dominant (resp. k-indépendant) si tout sommet extérieur à D a au moins k voisins dans D (resp. si le degré maximum du sous graphe induit par l’ensemble de sommets D est au plus k 1). La cardinalité minimum (resp. maximum) d’un ensemble k-dominant (resp. k-indépendant) de G est appelée le nombre de la k- domination (resp. le nombre de la k-indépendance) et est notée par k(G) (resp. k(G)). La détermination de ces deux paramètres dans les graphes en général est un problème difficile (NP-Complet). L’objectif principal de cette thèse est l’étude de ces deux paramètres et notre travail s’articule autour de trois axes, la détermination de bornes qui encadrent le plus possible ces paramètres, la caractérisation des graphes extrémaux et le statut ou l’état de chaque sommet vis-à-vis de ces deux paramètres. En effet, nous avons élaboré dans la première partie une généralisation d’une borne inférieure pour le paramètre k (G) déjà établie pour le nombre de 2-indépendance. Aussi on a fourni une caractérisation constructive des arbres extrémaux atteignant cette nouvelle borne pour k ≥ 2: Dans la deuxième partie nous avons donné la caractérisation des arbres tels que le nombre de 2-domination est égal au nombre de 2-indépendance. Dans la troisième partie, nous avons caractérisé les sommets appartenant à tout ou bien à aucun ensemble k-dominant minimum dans les arbres.