Etude de la K-domination, la K-indépendance et la K-domination romaine dans les graphes

Abstract

Soit G = (V; E) un graphe simple d’ordre n et de taille m o˘ V est l’ensemble des sommets et E l’ensemble des arêtes. Pour un entier k 1, un sous ensemble de sommets D de V est dit ensemble k-dominant de G si tout sommet de V D est adjacent ‡ au moins k sommets de D. On désigne par k (G) le cardinal minimum d’un ensemble k-dominant de G. Un sous ensemble de sommets S de V est dit ensemble k-indépendant de G si le degré maximum du sous graphe induit par S est au plus k 1, et on désigne par k (G) le cardinal d’un ensemble k-indépendant maximum de G. Une fonction de k-dominant romain sur G est une fonction f : V ! f0; 1; 2g telle que chaque sommet u pour lequel f(u) = 0 est adjacent ‡ au moins k sommets v1; v2; :::; vk avec f(vi) = 2 pour i = 1; 2; :::; k. Le poids d’une fonction de k-domination romaine est la valeur f(V ) = P u2V f(u), le poids minimum d’une fonction de k-domination romaine d’un graphe G est appelé le nombre de k-domination romaine de G et il est noté kR (G). Dans cette thèse, en premier lieu nous présentons de nouvelles inégalités entre les paramètres k (G), j (G) et (G) avec 1 j < k. Nous donnons quelques caractérisations des graphes extrémaux. Ensuite nous présentons des relations entre j (G) et (G), et nous donnons des caractérisations des graphes tels que j (G) = (G) pour j 2 f1; 2; 1; 1g. En second lieu nous étudions la k-domination romaine, us donnons des relations entre le nombre de k-domination romaine kR (G) et le nombre de domination romain R (G), de plus, nous donnons des caractérisations des graphes tel que kR(G) = R(G) + c, et nous caractérisons les graphes sans fK1;3; K1;3 + eg tels ue kR(G) = R(G) + t, avec t 2 f2k 3; 2k 2; n 3 g. Aussi nous étudions les graphes k-romains pour k 2. A la fin, nous étudiant la NP-complétude du problème de la k-domination romaine pour les graphes bipartis et les graphes sc