Contribution à l'étude de la domination double

Abstract

Notre objectif dans cette thèse est d’étudier les graphes critiques et les graphes stables par rapport a la domination double. Un dominant double dans un graphe ƒ• = (ƒÆƒ« ƒµ) est un ensemble de sommets ƒÃ . ƒÆ tel que tout sommet du graphe est ou bien dans ƒÃ et possède au moins un voisin dans ƒÃƒ« ou bien dans ƒÆ .ƒÃ et possède au moins deux voisins dans ƒÃƒª Le nombre de domination double de ƒ•ƒ« note „a¡Ñ2(ƒ•)ƒ« est le cardinal minimum d¡¦un ensemble dominant double de ƒ•ƒª Le graphe ƒ• est dit critique (respectivement, stable) par rapport a la domination double si „a¡Ñ2(ƒ•) change (respectivement, reste inchangé) suite a la suppression de n¡¦importe quel sommet, ou suite a l¡¦ajout ou la suppression de n¡¦importe quelle arête. Une partie de cette thèse est consacrée à la présentation des résultats antérieurs obtenus pour les graphes critiques et stables par rapport a la domination double. Nos contributions concernent en premier lieu les graphes dont le nombre de domination double augmente lorsque n¡¦importe quelle arête est supprimée, appelés graphes „a¡Ñ2-arête enlevée- critiques. Nous commençons par donner une condition nécessaire et suffisante les concernant, ensuite nous caractérisons les graphes réguliers, les arbres, les graphes sans ƒÀ4 et les graphes sans ƒÀ5ƒª Aussi, nous donnons des caractérisations des graphes „a¡Ñ2-arête-enlevée-critiques pour de petits nombres de domination double. En second lieu, nous abordons les graphes dont le nombre de domination double diminue quand n¡¦importe quel sommet qui n¡¦est pas un support est efface, appelés graphes „a¡Ñ2-sommet-critiques, et les graphes dont le nombre de domination double reste inchangé pour la même modification, appelés graphes „a¡Ñ2-sommet-stables. Nous montrons au début quelques propriétés relatives a ces deux familles de graphes. Nous donnons ensuite une caractérisation descriptive des arbres „a¡Ñ2-sommet-critiques et une caractérisation constructive de la famille de tous les arbres „a¡Ñ2-sommet-stables.