Sur la domination sommet-arête dans les graphes gonflés

Abstract

Le but de ce mémoire est l'étude du concept de domination sommet-arête, abrégé ve- domination, dans les graphes gonflés. Rappelons qu'un graphe G, est une inflation (graphe gonflé) d'un graphe G, si G, est obtenu à partir de G en remplaçant chaque sommet v de G, de degré d(v) par une clique Ka(), et en joignant deux sommets de cliques distinctes de G par une arête si et seulement si les sommets correspondants de G sont adjacents. Aussi, un sous ensemble de sommets D est un ve-dominant, si chaque arête e est ou bien incidente à un sommet de D ou adjacente à une arête incidente à un sommet de D. Le cardinal minimum d'un ensemble ve-dominant d'un graphe G est appelé nombre de ve-domination, et est noté par Yee (G). Dans ce mémoire, et en premier lieu, nous présentons quelques bornes inférieures et bornes supérieures, du nombre de ve-domination dans l'inflation Gr, d'un graphe G, en termes des caractéristiques du graphe G, ou en termes d'autres paramètres de domination du graphe G, avec des caractérisations des graphes extrémaux. Aussi on donne une caractérisation descriptive de la famille des arbres G dont le nombre de feuilles est égal au nombre de ve-domination supérieur de son inflation G. En second lieu, nous présontons une caractérisation des arbres G dont le nombre de domination est égal au nombre de ve-domination de son inflation G. Aussi nous donnons une caractérisation des graphes G dont le nombre de domination est égal au nombre de ve-domination de son inflation G, et est égal à A la fin, on donne des bornes supérieures du nombre de ve-domination pour l'inflation d'une grille Gmc pour m,c>2.