Contribution a l'etude de la ve-domination dans les graphes modifiés

Abstract

Notre travail dans ce mémoire porte sur l'étude de la domination sommet-arête, notée ve-domination, dans les graphes. Soit G = (V,E) un graphe simple, où V est l'ensemble des sommets et E est l'ensemble des arêtes. Un sous ensemble SCV est un ve-dominant de G, si chaque arête e de E est, ou bien incidente à un sommet de S ou adjacente à une arête incidente à un sommet de S. Le cardinal minimum d'un ensemble ve-dominant de G est appelé le nombre de ve-domination de G, noté ve(G). La contraction d'une arête uv dans un graphe G consiste à supprimer les sommets u et v de G en les remplaçant par un nouveau sommet noté par uv, et en attachant uv à tous les sommets qui sont adjacents à u ou v dans G. Le graphe obtenu à partir de G en contractant l'arête uv est noté par G. Dans ce mémoire nous avons montré que la contraction d'une arête quelconque de G fait diminuer par au plus une unité le nombre de ve-domination, mais ne peut pas l'augmenter. Un graphe G est dit ve-point-critique si ve (Guv) < Yve(G) pour toute arête uv dans E. Dans ce mémoire, nous nous sommes intéressés à l'étude de l'effet de la contraction d'une arête de E, sur le paramètre ve (G), où nous avons établi quelques conditions nécessaires pour les graphes e-point-critiques. Ainsi, nous avons fourni une caractérisation constructive des arbres e-point-critiques.