Contribution à l'étude de la k-domination, de la domination romaine et de la domination romaine double dans les digraphes

Abstract

L'étude de cette thèse comprend trois parties: Dans la première partie, de ce travail nous définissons une autre extension naturelle de la k-domination dans les graphes définie par Fink et Jacobson (1985), que nous appelons la k-domination dans les digraphes d'e nie comme suit. Un sous-ensemble S de sommets d'un digraphe D = (V; A) est un ensemble k-dominant si jN (u) \ Sj k pour chaque sommet u dans V S. Le nombre de k-domination de D, note k (D), est la cardinalité minimale d'un ensemble k-dominant dans D. Un k (D)-ensemble est un ensemble kdominant de D avec une cardinalité k (D). Ce nouveau concept est une extension du concept de domination dans les digraphes donne par Lee (1994). Aussi nous présentons quelques bornes inferieures et supérieures pour k (D). En particulier k (D) 2kn 2k+1 qui est une borne qui généralise (D) 2n 3 définie par Lee. En plus, nous caractérisons les digraphes pour lesquels ces bornes sont atteintes. Dans la deuxième partie de cette thèse, on s’intéresse à l'étude de la domination romaine dans les digraphes, notamment la borne supérieure R(D) n + (D) + 1 donné par Kamaraj et Jakkammal en 2011 et la borne supérieure de type Nordhaus-Gaddum R(D)+ R(D) n+3 donné par Chen, Hao et Xie en 2019. Dans cette partie nous caractérisons quelques classes spéciales de graphes orientes, satisfaisant R(D) = n +(D)+1. Aussi, nous caractérisons les digraphes D d’ordre n 1 satisfaisant R(D) + R(D) = n + 3. Puis, nous prouvons que le problème de décider si un graphe oriente D satisfait R(D) = n +(D) + 1 est Co NP-complet. Dans la troisième partie de cette thèse, on s’intéresse à l’étude de la domination romaine double dans les digraphes, notamment la borne supérieure R(D) 2 (n + (D)) + 1 et la borne supérieure de type Nordhaus - Gaddum dR(D) + dR (D) 2n+3 donné par Hao, Chen et Volkmann en 2019. Dans cette partie, nous caractérisons quelques classes spéciales de graphes orientés satisfaisant dR (D) = 2 (n +(D)) + 1. Aussi, nous caractérisons les digraphes D d’ordre n 1 satisfaisant dR (D) + dR(D) = 2n + 3 est atteinte.