Etude des invariants d'alliance dans quelques classes de graphes

Abstract

Dans cette thèse nous nous intéressons essentiellement au concept des alliances globales dans les graphes. Soit G = (V;E) un graphe simple, d'ensemble de sommets V et d'ensemble d'arêtes E. Un sous-ensemble S _ V est un dominant de G si tout sommet de V ?? S est adjacent à au moins un sommet de S. Un ensemble dominant S est une alliance offensive globale (aog) si pour tout sommet v dans V ?? S, jN[v] \ Sj _jN[v] \ (V ?? S)j ; et il est une alliance offensive globale forte(aogf) si l'inégalité est stricte. S est une alliance défensive globale (adg) si pour tout sommet v dans S, jN[v] \ Sj _jN[v] \ (V ?? S)j ; et il est une alliance défensive globale forte (adgf) si l'inégalité est stricte. On dit que S est une alliance puissante globale ou du à le (apg) s'il est à la fois une (aog) et une (adg).Le nombre de domination (G) est le cardinal minimum d'un ensemble dominant de G et le nombre d'alliance offensive globale o(G) (respectivement, le nombre d'alliance offensive globale forte ^o(G)) est le cardinal minimum d'une (aog) (respectivement, (aogf)) de G. Le nombre d'alliance défensive globale a(G) (respectivement, le nombre d'alliance défensive globale forte ^a(G)) est le cardinal minimum d'une (adg) (respectivement, (adgf)) de G. Le nombre d'alliance puissante globale ap (G) est le cardinal minimum d'une (apg) de G. L'étude de cette thèse comprend trois parties: Dans la première partie, nous montrons que tout graphe unicycle G d'ordre n avec ` feuilles et s sommets support satisfait o(G) _ (n ?? ` + s)=3: De plus nous caractérisons les graphes unicycles extrémaux atteignant cette borne inférieure. Dans la deuxième partie, nous donnons une caractérisation constructive de tous les arbres ayant une alliance offensive globale minimale unique (aogu-arbres). Dans la troisième partie, nous montrons que tout arbre T d'ordre n avec ` feuilles et s sommet s supports satisfait ap (T) _ (3n ?? 2` ?? s + 2)=5: De plus nous caractérisons tous les arbres extrémaux atteignant cette borne inférieure.