Noyaux et noyaux par chemins monochromatiques dans les graphes orientés

Abstract

Dans cette thèse, nous nous intéressons principalement à l'étude du concept du noyau dans les graphes orientés et nous étudions la j-indépendance et la p-domination dans un graphe non orienté. Le concept des noyaux a été introduit par Von Neumann et Morgenstern en 1944, comme une généralisation du concept de solutions pour les jeux coopératifs. Etant donné un graphe orienté D= (V, A), un sous-ensemble N ? V est un noyau, s'il est indépendant (ses sommets sont non adjacents deux à deux) et absorbant (tout sommet qui n'appartient pas à N a au moins un successeur dans cet ensemble). Nous commençons par étudier le problème de la caractérisation des graphes non orientés contenant un sous-ensemble qui est à la fois j-indépendant et p-dominant pour deux entiers positifs p, j = ?. Dans un graphe non orienté G= (V, E), un ensemble j-indépendant est un sous-ensemble S de V tel que le degré maximum dans le sous-graphe induit par les sommets de S est au plus j-1, et il est p-dominant si pour tout sommet v ? V\S, |N(v)nS| = p. Nous caractérisons les arbres T satisfaisant ?p(T)=ßj(T) (?p(T) est le cardinal minimum d'un ensemble p-dominant de T, ßj(T) est Le cardinal maximum d'un ensemble j-indépendant de T) pour p, j deux entiers positifs tels que 1 = j < p = ?. Ensuite, nous présentons un nouveau concept "(k,l)-plus-noyau dans les graphes orientés", pour lequel des résultats classiques sur les noyaux dans les graphes orientés sont généralisés. Nous proposons une généralisation de la fonction de Grundy et nous donnons une condition nécessaire et suffisante pour qu'un digraphe ait un noyau.