Etude de quelques invariants de graphes

Abstract

L'objet principal de cette thèse est l'étude de quelques aspects théoriques des problèmes liés à la théorie de la domination dans les graphes. Un sous-ensemble S de sommets d'un graphe G=(V,E) est dit dominant si tout sommet de V−S est adjacent à au moins un sommet de S. Le nombre de domination γ(G) est le cardinal minimum d'un ensemble dominant de G. La détermination de γ(G) dans un graphe quelconque est extrêmement difficile. Plusieurs types de domination sont définis en imposant des propriétés supplémentaires sur les ensembles dominants, citons la domination stable, double et couplée dont les paramètres associés sont désignés respectivement par i(G), γ×2(G ) et γpr(G ).On commence par établir une nouvelle borne supérieure pour i(G) améliorant la célèbre et vieille borne de Claude Berge établie pour γ(G). Ensuite on caractérise les arbres extrémaux atteignant la borne pour les deux paramètres ainsi qu'une caractérisation des graphes réguliers atteignant la borne sur γ(G). D'autres résultats sont obtenus en conséquence de cette nouvelle borne pour la somme et le produit des paramètres de domination inférieurs et le nombre chromatique d'un graphe. On entame par la suite l'étude de la domination double où on établit une condition nécessaire et suffisante pour la minimalité (au sens de l'inclusion) des ensembles dominants doubles ainsi que divers bornes sur γ×2(G), en particulier dans le cas des arbres, suivies par des caractérisations des arbres extrémaux. On initie l'étude de la domination double exacte dans les graphes. On montre que le problème d'existence d'un ensemble dominant double exact est NP-complet en général et nous caractérisons par construction les arbres admettant de tels ensembles. Concernant la domination couplée, nous citons en particulier une caractérisation par construction des arbres admettant un ensemble dominant couplé minimum unique. Nous montrons que γ×2(G)≥γpr(G) si G est sans griffes ou bien un arbre non trivial et nous caractérisons les arbres extrémaux pour l'égalité.