Veuillez utiliser cette adresse pour citer ce document : https://di.univ-blida.dz/jspui/handle/123456789/8744
Titre: Sur une généralisation de la domination dans les graphes
Auteur(s): Attalah, Karima
Mots-clés: Graphe
K-Domination dans les graphes
Date de publication: 2020
Editeur: Univ-Blida1
Résumé: L’objet principal de cette thèse est l’étude de la k-domination dans les graphes ainsi que l’effet de la contraction d’une arête quelconque sur le nombre de 2-domination d’un graphe. Etant donné un graphe connexe non trivial G = (V; E) d’ordre n et soit k un entier, un sous ensemble D V est un k-dominant de G si tout sommet de V (G) D est adjacent à au moins k sommets de D: Si de plus le sous graphe induit par D est connexe nous parlerons d’un ensemble k-dominant connexe de G. Le nombre de k-domination (connexe) k (G) (resp. c k (G)) est le cardinal minimum d’un ensemble k-dominant (connexe) de G: Dans cette thèse, nous nous concentrons en premier lieu sur la caractérisation des graphes vérifiant des égalités qui existent dans la littérature sous forme de problèmes ouverts. Nous donnons quelques propriétés des graphes connexes G d’ordre n tels que c k (G) = n 2: Ensuite, nous fournissons une caractérisation complète des graphes connexes cubiques G tels que c 2 (G) = n 2 et des graphes connexes 4-réguliers sans griffes tels que c 3 (G) = n 2: D’autre part, nous traitons le problème de la caractérisation des graphes connexes G vérifiant c 2 (G) = (G)+1 ou c 3 (G) = (G)+2 pour certaines classes de graphes: les graphes pour lesquels (G) = 1; ou qui sont de maille d’au moins 5, les graphes sans griffes et les graphes sans triangles maximaux. En second lieu; nous nous intéressons à l’effet de la contraction d’une arête (identification de deux sommets adjacents) sur le nombre de 2-domination. Nous donnons en particulier une caractérisation constructive des arbres dont le nombre de 2-domination diminue (resp. ne change pas) par l’effet de la contraction d’une arête quelconque de l’arbre.
Description: 107 p. : ill. ; 30 cm.
URI/URL: http://di.univ-blida.dz:8080/jspui/handle/123456789/8744
Collection(s) :Thèse de Doctorat

Fichier(s) constituant ce document :
Fichier Description TailleFormat 
32-510-153-1.pdfThèse de Doctorat1,56 MBAdobe PDFVoir/Ouvrir


Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.