Sur les alliances dans les graphes

Abstract

L'objet principal de ce mémoire est l'étude des alliances globales dans les graphes. Soit G = (V, E) un graphe simple, d'ensemble de sommets V et d'ensemble s d'arêtes E ensemble de 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, |N[v]∩S|≥|N[v]∩(V-S)|. S est une alliance défensive globale (adg) si pour tout sommet v dans S, |N[v]∩S|≥|N[v]∩(V-S)|. Le nombre de domination γ(G) est le cardinal minimum d'un ensemble dominant de G et le nombre d'alliance offensive globale γo (G) est le cardinal minimum d'une (aog) de G. Le nombre d'alliance défensive globale γa (G) est le cardinal minimum d'une (adg) e G Dans ce mémoire, on exposera en premier lieu notre contribution à l'étude des alliances globales dans les arbres. On montre que tout arbre T d'ordre au moins trois avec ℓ sommets de degré et s sommets supports satisfait γo (T) n-ℓ+s+1) 3. Par ailleurs on caractérise les arbres extrémaux atteignant cette borne inférieure, ainsi qu'une caractérisation des arbres pour lesquels le nombre de domination et le nombre d'alliance offensive globale sont égaux.