Sur une généralisation de la domination dans les graphes

Abstract

L’objet principal de cette thèse est l’étude de la k-domination dans les graphes ainsi que l’effet de la contraction d’une arête quelconque sur le nombre de 2-domination d’un graphe. Etant donné un graphe connexe non trivial G = (V; E) d’ordre n et soit k un entier, un sous ensemble D V est un k-dominant de G si tout sommet de V (G) D est adjacent à au moins k sommets de D: Si de plus le sous graphe induit par D est connexe nous parlerons d’un ensemble k-dominant connexe de G. Le nombre de k-domination (connexe) k (G) (resp. c k (G)) est le cardinal minimum d’un ensemble k-dominant (connexe) de G: Dans cette thèse, nous nous concentrons en premier lieu sur la caractérisation des graphes vérifiant des égalités qui existent dans la littérature sous forme de problèmes ouverts. Nous donnons quelques propriétés des graphes connexes G d’ordre n tels que c k (G) = n 2: Ensuite, nous fournissons une caractérisation complète des graphes connexes cubiques G tels que c 2 (G) = n 2 et des graphes connexes 4-réguliers sans griffes tels que c 3 (G) = n 2: D’autre part, nous traitons le problème de la caractérisation des graphes connexes G vérifiant c 2 (G) = (G)+1 ou c 3 (G) = (G)+2 pour certaines classes de graphes: les graphes pour lesquels (G) = 1; ou qui sont de maille d’au moins 5, les graphes sans griffes et les graphes sans triangles maximaux. En second lieu; nous nous intéressons à l’effet de la contraction d’une arête (identification de deux sommets adjacents) sur le nombre de 2-domination. Nous donnons en particulier une caractérisation constructive des arbres dont le nombre de 2-domination diminue (resp. ne change pas) par l’effet de la contraction d’une arête quelconque de l’arbre.