L'arête-domination et l'rête-domination indépendante dans les arbres

Abstract

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.