Veuillez utiliser cette adresse pour citer ce document : https://di.univ-blida.dz/jspui/handle/123456789/12845
Affichage complet
Élément Dublin CoreValeurLangue
dc.contributor.authorMeddaha, Ncera-
dc.date.accessioned2021-11-10T08:26:32Z-
dc.date.available2021-11-10T08:26:32Z-
dc.date.issued2014-
dc.identifier.urihttp://di.univ-blida.dz:8080/jspui/handle/123456789/12845-
dc.description106 p. : ill. ; 30 cm.fr_FR
dc.description.abstractSoit G = (V; E) un graphe simple et k un entier positif. Un sous ensemble de sommets D dans le graphe G est dit k-dominant (resp. k-indépendant) si tout sommet extérieur à D a au moins k voisins dans D (resp. si le degré maximum du sous graphe induit par l’ensemble de sommets D est au plus k 1). La cardinalité minimum (resp. maximum) d’un ensemble k-dominant (resp. k-indépendant) de G est appelée le nombre de la k- domination (resp. le nombre de la k-indépendance) et est notée par k(G) (resp. k(G)). La détermination de ces deux paramètres dans les graphes en général est un problème difficile (NP-Complet). L’objectif principal de cette thèse est l’étude de ces deux paramètres et notre travail s’articule autour de trois axes, la détermination de bornes qui encadrent le plus possible ces paramètres, la caractérisation des graphes extrémaux et le statut ou l’état de chaque sommet vis-à-vis de ces deux paramètres. En effet, nous avons élaboré dans la première partie une généralisation d’une borne inférieure pour le paramètre k (G) déjà établie pour le nombre de 2-indépendance. Aussi on a fourni une caractérisation constructive des arbres extrémaux atteignant cette nouvelle borne pour k ≥ 2: Dans la deuxième partie nous avons donné la caractérisation des arbres tels que le nombre de 2-domination est égal au nombre de 2-indépendance. Dans la troisième partie, nous avons caractérisé les sommets appartenant à tout ou bien à aucun ensemble k-dominant minimum dans les arbres.fr_FR
dc.language.isofrfr_FR
dc.publisherUniv.Blida 1fr_FR
dc.subjectGraphesfr_FR
dc.subjectK-Dominationfr_FR
dc.subjectK-Indépendancefr_FR
dc.subjectArbres extrémauxfr_FR
dc.titleLa K-domination et la K-indépendance dans les graphesfr_FR
dc.typeThesisfr_FR
Collection(s) :Thèse de Doctorat

Fichier(s) constituant ce document :
Fichier Description TailleFormat 
32-510-146-1.pdfThèse de Doctorat799,35 kBAdobe PDFVoir/Ouvrir


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