Domination et irrédondance dans les graphes orientés

Abstract

Dans ce mémoire, nous nous intéressons principalement à l'étude des paramètres de domination dans les graphes orientés. Dans un premier temps, nous donnons deux nouvelles bornes supérieures pour le nombre de domination !"#$, une condition nécessaire pour que la borne supérieure de !"#$ % &"#$ ' Δ)"#$ ' *)"#$ soit vraie et nous montrons que cette borne est atteinte pour les chemins et les circuits orientés anti symétriquement. Ensuite on caractérise les chaines, les cycles et les arbres orientés pour lesquels la borne supérieure de !"#$ % &"#$ ' +,"#$ est atteinte (où +,"#$ est la cardinalité d'un couplage maximum dans le graphe orienté D). On donne ensuite une nouvelle borne inférieure pour le nombre de domination !"#$ à savoir -"#$ % !"#$ (où -"#$ est le nombre de sommets supports dans #) puis on caractérise les graphes orientés pour lesquels la borne inférieure de -"#$ % !"#$ est atteinte, aussi la caractérisation des graphes orientés pour lesquels !"#$ . -"#$ . &"#$ ' +,"#$. Dans un second temps, on donne une nouvelle borne inférieure pour le nombre d'irrédondance inférieur à savoir /0"#$ 1 -"#$. Ensuite nous donnons les valeurs exactes de /0"#$ pour les chemins et les circuits orientés anti symétriquement, puis la caractérisation des graphes orientés pour lesquels /0"#$ . -"#$ . &"#$ ' +,"#$. Enfin, nous donnons une nouvelle borne supérieure pour le nombre d'irrédondance supérieur à savoir 23"#$ % &"#$ ' 1. Ensuite nous caractérisons les graphes orientés pour lesquels 23"#$ . &"#$ ' 1, et nous donnons des conditions nécessaires pour que les bornes des deux inégalités /0"#$ % +,"#$ % 23"#$ soient vraies et nous montrons que ces bornes sont atteintes. Nous terminons ce mémoire en donnant quelques perspectives et travaux futurs dans ce domaine de recherche.