Contribution A L'étude De La Domination Double
Résumé: Notre objectif dans cette these est d¡¦etudier 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 possede au moins un voisin dans ƒÃƒ« ou bien dans ƒÆ .ƒÃ et possede 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 inchange) suite a la suppression de n¡¦importe quel sommet, ou suite a l¡¦ajout ou la suppression de n¡¦importe quelle arete. Une partie de cette these est consacree a la presentation des resultats anterieurs 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 arete est supprimee, appeles graphes „a¡Ñ2-areteenlevee- critiques. Nous commencons par donner une condition necessaire et suffisante les concernant, ensuite nous caracterisons les graphes reguliers, les arbres, les graphes sans ƒÀ4 et les graphes sans ƒÀ5ƒª Aussi, nous donnons des caracterisations des graphes „a¡Ñ2-arete-enlevee-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, appeles graphes „a¡Ñ2-sommet-critiques, et les graphes dont le nombre de domination double reste inchange pour la meme modification, appeles graphes „a¡Ñ2-sommet-stables. Nous montrons au debut quelques proprietes relatives a ces deux familles de graphes. Nous donnons ensuite une caracterisation descriptive des arbres „a¡Ñ2-sommet-critiques et une caracterisation constructive de la famille de tous les arbres „a¡Ñ2-sommet-stables.
Mots-clès:
Nos services universitaires et académiques
Thèses-Algérie vous propose ses divers services d’édition: mise en page, révision, correction, traduction, analyse du plagiat, ainsi que la réalisation des supports graphiques et de présentation (Slideshows).
Obtenez dès à présent et en toute facilité votre devis gratuit et une estimation de la durée de réalisation et bénéficiez d'une qualité de travail irréprochable et d'un temps de livraison imbattable!
Aucun fichier associé
Si le fichier est volumineux, l'affichage peut échouer. Vous pouvez obtenir le fichier directement en cliquant sur le bouton "Télécharger".
