L’arête - Domination et la 2-indépendance dans les arbres

Abstract

Soit G = (V; E) un graphe simple. Un sous ensemble D de E(G) est dit arŒtedominant de G si toute arŒte e 2 E(G) est dans D ou elle est adjacente à au moins une arØte e 0 2 D: La cardinalitØ minimum d un ensemble arŒte-dominant de G est appelØe le nombre de l arŒte-domination et est notØe par

0 (G). Un sous ensemble S de V est un 2-indØpendant de G si le degrØ maximum de sous graphe induit par S est au plus 1 i-e (S) 1. La cardinalitØ maximum d un ensemble 2-indØpendant de G est appelØe le nombre de 2-indØpendance et est notØe par 2 (G) Dans ce mØmoire on s intØresse à Øtudier ces deux paramŁtres, et notre travail consiste à Øtablir une nouvelle borne infØrieur de 2 en fonction de

0 dans les arbres. Aussi on a fourni une caractØrisation constructive des arbres extrØmaux atteignant cette nouvelle borne. On note de tels arbres par ( 2 ; 2

0 )arbres. En n, nous montrons que cette borne n est pas satisfaite de maniŁre gØnØrale.