Veuillez utiliser cette adresse pour citer ce document :
https://di.univ-blida.dz/jspui/handle/123456789/4260
Titre: | Sur quelques invariants de domination dans les graphes |
Auteur(s): | Boutrig, Razika |
Mots-clés: | GRAPHES Domination |
Date de publication: | 2011 |
Editeur: | univ- blida 1 |
Résumé: | Nous nous sommes intÈressÈs dans ce mÈmoire ‡ líÈtude de la domination forte et faible dans les graphes. Soit G = (V; E) un graphe simple díordre n, o˘ V est líensemble des sommets et ensemble des arÍtes. Un sous ensemble D V est un dominant faible (resp, fort) de G si chaque sommet v 2 V D est adjacent ‡ un sommet u 2 D, o˘ deg(v) deg(u) (respÇ deg(v) deg(u)): Le cardinal minimum díun ensemble dominant faible (resp, fort) de G est appelÈ le nombre de domination faible (resp, forte), notÈ par w(G) (resp, s(G)) de Dans ce mÈmoire, on commence par prÈsenter quelques bornes superieures sur les paramËtres de domination forte et faible amÈliorant les bornes de Domke, Hattingh, Markus et Ungerer. Ainsi quíune caractÈrisation des arbres pour lesquels le nombre de domination et le nombre de dominaton forte sont Ègaux.Dans un second lieu, nous montrons que si G est un graphe connexe díordre n 3; alors w(G) + ts(G) n; o˘ t = +13 pour tout graphe G, t = 35 si G est un graphe bloc et t = 32 si G est un graphe sans gri§es. En dernier lieu, nous Ètudions díune faÁon brËve la k-domination forte et faible dÈÖnie comme suit: Soit k 1 un entier. Un sous ensemble D V est un k-dominant fort (resp, faible) de G si tout sommet v de V D est k-dominÈ fortement (respÇfaiblement) par un sommet de D. Le nombre de k-domination forte (respÇnombre de k-domination faible); notÈ par sk (G) (resp, wk (G)) est le cardinal minimum díun ensemble k-dominant fort (resp, faible) de G: Pour k = 1Çon retrouve la dÈÖnition de la domination forte et faible usuelle. Donc pour tout GÇs1 (G) = s (G) et w1 (G) = w (G) : Quelques rÈsultats intÈrÈssants sont obtenus dans ce sens, en particulier on prÈsente quelques bornes et propriÈtÈs sur la k-domination forte et faible. On montre que pour tout graphe connexe G tel que s (G) 2 (resp, w (G) 2) et pour tout entier k 4, sk (G) < s (G) (resp, wk (G) < w (G)). On donne aussi une condition nÈcÈssaire pour les graphes G tels que 3s (G) = s (G) et nous caractÈrisons díune faÁon descriptive des chenilles T telles que 3s (T ) = s (T ) : |
Description: | 63p. Ill. 4 CD. 30cm |
URI/URL: | http://di.univ-blida.dz:8080/jspui/handle/123456789/4260 |
Collection(s) : | Thèse de Magister |
Fichier(s) constituant ce document :
Fichier | Description | Taille | Format | |
---|---|---|---|---|
32-510-115-1.pdf | these magister | 806,78 kB | Adobe PDF | Voir/Ouvrir |
Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.