Contribution a l'étude de la k-domination et la k-indépendance dans les graphes

Abstract

Soit G = (V;E) un graphe simple d’ordre n et de taille m où V (G)est l’ensemble des sommets et E(G) 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 nD est adjacent à au moins k sommet de D. On désigne par k(G) la taille d’un k..dominant minimum 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) la taille d’un k-indépendant maximum de G: Un sous ensemble de sommets S de V est dit ensemble k..co-indépendant de G s’il est k..indépendant dans G: Et On désigne par !k(G) la taille d’un k..Co-indépendant maximum de G. Comme chaque ensemble k..indépendant est (k + 1)..indépendant et chaque ensemble (k + 1)..dominant est k-dominant, les séquences (k); (k) et (!k) sont faiblement croissantes: On note par ¬k(G) la partition minimum de V en k-indépendant et on l’appelle le nombre k-chromatique, et on note par k(G) la partition minimum de V en k-co-indépendant. Les séquences (¬k) et ( k) sont faiblement décroissantes. Dans ce mémoire, en premier lieu on présente des relations entre les paramètres k(G), !k(G), ¬k(G) et k(G); des bornes pour le nombre k..chromatique, des nouvelles bornes pour le nombre de k..indépendance en fonction de n;m; et k. et des relations de type Nordhaus- Gaddum pour k et ¬k: Dans un second lieu, on étudie les séquences (k) et (k) qui sont strictement croissantes dans certaines classes de graphes réguliers. En n, on caractérise les graphes sans fK1;3;K1;3 + eg tels que k (G) < k+1(G) et k(G) < k+1(G):