Résumé:
SoitG= (V;E) un graphe simple. Un sous ensembleDdeE(G) est dit arÍte-
dominant deGsi toute arÍte e2E(G)nDest adjacente ‡ au moins une arÈte e
0
2D:
Un ensemble arÍte-dominant est ainsi un sous ensemble des arÍtes qui dominent toutes
les arÍtes de G:La cardinalitÈ minimum díun ensemble arÍte-dominant deGest appelÈe
le nombre de líarÍte-domination et est notÈe par
0
(G). Un ensemble arÍte-dominant
avec une telle cardinalitÈ est appelÈ
0
(G)-ensemble: Un sous ensembleSdeEest un
arÍte-dominant indÈpendant deGsi toutes ses arÍtes sont deux-‡-deux non-adjacentes.
La cardinalitÈ minimum díun ensemble arÍte-dominant indÈpendant maximal est appelÈe
le nombre díarÍte-domination indÈpendante infÈrieur de G, et est notÈe par i
0
(G): La
dÈtermination de ces deux paramËtres dans les graphes en gÈnÈral est un problËme di¢ cile
(NP-Complet). Notre objectif principal dans ce mÈmoire est líÈtude de ces deux paramËtres et notre
travail síarticule autour de la caractÈrisation des arbres T (resp. chaÓnes) tels que le
nombre de líarÍte-domination
0
(T) est fortement Ègal au nombre de líarÍte-domination
indÈpendance infÈrieur i
0
(T) i.e
0
(T) i
0
(T): On note de tels arbres par(
0
;i
0
) arbres
et de telles chaÓnes par(
0
;i
0
) chaÓnes. LetG= (V;E)be a simple graph. A subsetDofE(G)is an edge dominating of Gif
any edgee2E(G)nDis adjacent to at least one edge e2D:Thus, an edge dominating set
is a subset of the edges which dominate all the other edges of G:The minimum cardinality
of an edge dominating set ofGis called edge domination number and is denoted by
0
(G).
An edge dominating set with such a cardinality is called
0
(G) set. A subset Sof
E(G)is an edge independent dominating if all its edges are two-by-two non-adjacent. The
minimum cardinality of a maximal independent edge dominating set is called the lower
number of independent edge domination ofG;and is denoted byi
0
(G): The determination
of these two parameters in graphs in general is a di¢ cult problem (NP-complete).
Our main objective in this thesis is the study of these two parameters and our work
revolves around the characterization of treesT(resp. paths) such that the number of edge
domination
0
(T) is strongly equal to the number of lower independent edge domination
i
0
(T)ie
0
(T) i
0
(T). We note such trees by(
0
;i
0
) trees and such paths by(
0
;i
0
) paths.
