Contribution à l'étude de la K-indépendance dans les graphes

Abstract

Soit G = (V, E) un graphe simple. Un sous ensemble S de V est dit dominant de G, si tout sommet de V-S est voisin d’au moins un sommet dans S. On note la cardinalité minimum d’un ensemble dominant de G par γ(G). Lorsqu’on impose des conditions supplémentaires à l’ensemble dominant, on obtient d’autres types de domination. Par exemple, si on impose que tout sommet de V-S possède au moins k voisins dans S, on aura la k-domination et si on impose que le degré maximum du sous graphe induit par l’ensemble de sommets S est au plus k-1, on aura la k-indépendance. Dans cette thèse, on s’intéresse à l’étude de la k-indépendance et la k-domination dans les graphes, on établit des bornes pour les paramètres associés à la k-domination et la k indépendance, à savoir γk(G), Γk(G), ik(G) et βk(G). Enfin on caractérise les graphes extrémaux atteignant certaines bornes dans le cas de certaines classes de graphes simples comme les arbres et les cactus.