Veuillez utiliser cette adresse pour citer ce document : https://di.univ-blida.dz/jspui/handle/123456789/12845
Titre: La K-domination et la K-indépendance dans les graphes
Auteur(s): Meddaha, Ncera
Mots-clés: Graphes
k-domination
k-indépendance
Arbres extrémaux
Date de publication: 2014
Editeur: univ.blida 1
Référence bibliographique: Blida
Résumé: Soit 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.
Description: Bibliogr. + 4 cd rom.106 p.
URI/URL: http://di.univ-blida.dz:8080/jspui/handle/123456789/12845
Collection(s) :theses 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.