Etude des ensembles sommets-arêtes et arêtes-sommets dominants dans les graphes

Abstract

L’objet principal de cette thèse est l’étude de la domination sommet-arête dans les graphes. Etant donné un graphe connexe non trivial G = (V; E), un sous ensemble D V est un dominant sommet-arête, abrégé ve-dominant, de G si chaque arête e 2 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 de G est appelé le nombre de ve-domination, noté par ve (G). Dans cette thèse, nous présentons en premier lieu des relations liant la ve-domination avec quelques paramètres de domination, répondant ainsi ‡ quatre questions posées dans la thèse de PhD de Lewis. On établit par la suite des bornes supérieures sur ve (G) et ive(G), o˘ on donne une borne supérieure sur ive(G) en fonction de ve (G) pour tout graphe connexe non trivial et sans K1;k, avec k 3. Par ailleurs, on montre que le nombre de ve-domination indépendante est au plus égal à la moitié du nombre de domination totale pour tout graphe biparti, et on montre que n=3 est aussi une borne supérieure sur le nombre de ve-domination des graphes connexes d’ordre n ≥ 3 et sans C5, améliorant une récente borne donnée pour les arbres. D’autre part, on caractérise les graphes G tels que R(G) = 2 ve (G). En second lieu, on introduit et on initie l’étude de la ve-domination totale dans les graphes dont le paramètre associé est noté t ve (G). On montre que le problème de décision associé à la ve-domination totale est NP-complet pour les graphes bipartis. On montre par la suite que si T est un arbre d’ordre n différent d’une étoile avec ` feuilles et s sommets supports, alors t ve (T) ≥ (n + s) =2. Par ailleurs, on caractérise les arbres atteignant cette borne supérieure. D’autre part, on établit une condition nécessaire pour les graphes connexes non triviaux G tels que t ve (G) = 2 ve (G) et on donne une caractérisation constructive des arbres T satisfaisant t ve (T) = 2 ve (T). En dernier lieu, nous étudions d’une façon brève la domination arête-sommet. Un sous ensemble F E est un dominant arête-sommet, (abrégé ev-dominant) de G si tout sommet v 2 V, est ev-dominé par au moins une arête de F. Le cardinal minimum d’un ensemble ev-dominant de G est appelé le nombre de ev-domination de G, noté ev (G).