Veuillez utiliser cette adresse pour citer ce document : https://di.univ-blida.dz/jspui/handle/123456789/754
Affichage complet
Élément Dublin CoreValeurLangue
dc.contributor.authorChellali, Mustapha-
dc.date.accessioned2019-10-13T12:53:33Z-
dc.date.available2019-10-13T12:53:33Z-
dc.date.issued2005-
dc.identifier.urihttp://di.univ-blida.dz:8080/xmlui/handle/123456789/754-
dc.description106 p.- 4 cd-rom, ill.- 30 cm.fr_FR
dc.description.abstractL'objet principal de cette thèse est l'étude de quelques aspects théoriques des problèmes liés à la théorie de la domination dans les graphes. Un sous-ensemble S de sommets d'un graphe G=(V,E) est dit dominant si tout sommet de V−S est adjacent à au moins un sommet de S. Le nombre de domination γ(G) est le cardinal minimum d'un ensemble dominant de G. La détermination de γ(G) dans un graphe quelconque est extrêmement difficile. Plusieurs types de domination sont définis en imposant des propriétés supplémentaires sur les ensembles dominants, citons la domination stable, double et couplée dont les paramètres associés sont désignés respectivement par i(G), γ×2(G ) et γpr(G ).On commence par établir une nouvelle borne supérieure pour i(G) améliorant la célèbre et vieille borne de Claude Berge établie pour γ(G). Ensuite on caractérise les arbres extrémaux atteignant la borne pour les deux paramètres ainsi qu'une caractérisation des graphes réguliers atteignant la borne sur γ(G). D'autres résultats sont obtenus en conséquence de cette nouvelle borne pour la somme et le produit des paramètres de domination inférieurs et le nombre chromatique d'un graphe. On entame par la suite l'étude de la domination double où on établit une condition nécessaire et suffisante pour la minimalité (au sens de l'inclusion) des ensembles dominants doubles ainsi que divers bornes sur γ×2(G), en particulier dans le cas des arbres, suivies par des caractérisations des arbres extrémaux. On initie l'étude de la domination double exacte dans les graphes. On montre que le problème d'existence d'un ensemble dominant double exact est NP-complet en général et nous caractérisons par construction les arbres admettant de tels ensembles. Concernant la domination couplée, nous citons en particulier une caractérisation par construction des arbres admettant un ensemble dominant couplé minimum unique. Nous montrons que γ×2(G)≥γpr(G) si G est sans griffes ou bien un arbre non trivial et nous caractérisons les arbres extrémaux pour l'égalité.fr_FR
dc.language.isofrfr_FR
dc.publisherUniv- Blida 1fr_FR
dc.subjectInvariantsfr_FR
dc.subjectGraphesfr_FR
dc.titleEtude de quelques invariants de graphesfr_FR
dc.typeThesisfr_FR
Collection(s) :Thèse de Doctorat

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


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