Etude de l'effet de la séparation des arêtes sur la domination double dans les graphes

Abstract

Soient u et v deux sommets à distance deux dans un graphe G sans sommets isolØs et soit x un voisin commun à u et v de degrØ au moins trois. Notons par A(G) l ensemble de toutes les chaines induites par de tels sommets. L action de sØparation des arŒtes suivant la chaine uxv consiste à supprimer les arŒtes ux et vx et ajouter l arŒte uv: Dans ce mØmoire, on Øtudie l e⁄et de la sØparation d arŒtes sur le nombre de domination double d un graphe G dØ ni comme Øtant le cardinal minimum d un ensemble de sommets S tel que tout sommet de S possŁde au moins un voisin dans S et tout sommet de V S possŁde au moins deux voisins dans S: On montre que la sØparation des arŒtes peut l augmenter par au plus 2 et le diminuer par au plus 1: En consØquence, cinq familles de graphes sont dØ nies, oø on montre à travers des exemples de graphes, parfois d arbres, que ces classes ne sont pas vides. D autre part, on donne une condition nØcessaire et su¢ sante pour qu une chaine de A(G) diminue le nombre de domination double du graphe G: Une attention particuliŁre a ØtØ rØservØe aux classes de graphes G dont la sØparation de toute arŒte de A(G) diminue le nombre de domination double de G: