Etude De L'indice De Criticite Du Nombre De La 2-domination Dans Certains Graphes

Résumé: Soit G = (V ;E) un graphe simple d'ordre n et de taille m o uV (G) est l'ensemble des sommets et E(G) l'ensemble des ar^etes. Un sous ensemble de sommets S de V est dit ensemble 2-domination de G si tout sommet de V 􀀀S est adjacent a au moins deux sommet dans S , et on d esigne par 2(G) la taille minimum d'un 2-domination minimal de G. Pour un graphe G, nous d e nissons l'indice de criticit e d'un sommet v 2 V comme civ 2(v) = 2(G) 􀀀 2(G 􀀀 v). et l'indice de criticit e de la suppression d'un sommet dans un graphe G est d e ni comme civ 2(G) = 􀀀Pn i=1 civ 2(v) =n(G). de m^eme, nous d e nissons , et l'indice de criticit e de la suppression d'une ar^ete e 2 E(G) comme ci􀀀 2(e) = 2(G)􀀀 2(G􀀀e). L'indice de criticit e de la suppression d'une arr^ete dans un graphe G est d e ni comme ci􀀀 2(G) = 􀀀Pm i=1 ci􀀀 2(e) =m(G).Nous d e nissons aussi l'indice de criticit e de l'ajout d'une ar^ete e 2 E(G) comme ci+ 2(e) = 2(G) 􀀀 2(G + e), et l'indice de criticit e de l'ajout d'une ar^ete dans un graphe G d e ni comme ci+ 2(G) = Pm i=1 ci+ 2(e) =m(G) . Dans ce m emoire, nous d eterminons l'indice de criticit e de la suppression d'un sommet, et ensuite nous d eterminons l'indice de criticit e de la suppression et l'ajout d'une ar^ete de la 2-domination pour les cha^ nes et les cycles.

Publié dans la revue: