Etude de la [j,k]-domination et la [j,k]-indépendance dans les graphes

Abstract

Soit G = (V;E) un graphe simple d'ordre n et soient j et k deux entiers positifs tels que j _ k. Un sous-ensemble S de V est un [j; k]-ensemble de G si tout sommet v de V ??S est adjacent à au moins j sommets et à au plus k sommets dans S. Le cardinal minimum d'un [j; k]-ensemble de G est désigné par [j;k] (G). Si de plus S est indépendant, alors S est dit un [j; k]-ensemble indépendant où i[j;k](G) et _[j;k] (G) désignent, respectivement, les cardinaux minimum et maximum d'un [j; k]-ensemble indépendant de G. Dans cette thèse, nous nous sommes intéressés par l'étude des [j; k]-ensembles dans les graphes. Nous commençons par quelques propriétés sur les [j; k]-ensembles disjoints. En outre, nous nous intéressons à la caractérisation des graphes G d'ordre n tels que [j;k] (G) 2 fnn ?? 1g pour k 2 f_;_ ?? 1;_ ?? 2g. Nous donnons également des conditions suffisantes pour les graphes G d'ordre n tels que [j;k] (G) < n. A la .n, nous montrons que le problème de décision correspondant à la détermination de [j; k] (G), pour 2 _ j _ k, est NP-complet dans les graphes bipartis. La dernière partie de cette thèse a été consacrée à l'étude des [j; k]-ensembles indépendants. Nous avons établi une condition nécessaire et su¢ sante pour l'existence d'un [1; k]-ensemble indépendant dans un graphe. De plus, les graphes scindés admettant de tels ensembles ont été caractérisés. D'autre part, des bornes ont été déterminées pour _[1;k](G) et i[1;k](G), ainsi que des relations de type Nordhaus-Gaddum. Enfin, la NP-complétude du problème de décision associé à la détermination de _[1;k](G) a été montré pour les graphes bipartis et triangulés.