Contribution à l'étude des graphes u-point critiques

Abstract

Soit G=(V,E) un graphe simple d'ordre n où V est l'ensemble des sommets et E l'ensemble des arêtes. L'objet principal de ce mémoire est l'étude de l'effet de la contraction d'une arête ou l'identification d'un couple de sommets sur certains paramètres de graphes, citons le couplage maximum β1(G), le nombre de domination connexe γc(G), le nombre de (stabilité β₀(G) et le nombre de domination stable i(G). Etant donné un paramètre μ d'un graphe G, nous dirons que G est μ-point critique si μ(Gab)<μ(G) pour toute arête ab∈E(G) et G est totalement μ-point critique si μ(Gab)<μ(G) pour tout couple de sommets (a,b)∈V×V, où Gab est le graphe obtenu .par la contraction de l'arête ab ou l'identification de a et b. Dans ce mémoire, on commence par caractériser les graphes (totalement) β₁-point critique. Ensuite, on caractérise quelques classes de graphes (totalement) γc-point critiques, en particulier les graphes blocs, les graphes cactus, les graphes scindés et les graphes ayant γc(G)=2. Pour μ=β₀, on établit une condition nécessaire et suffisante pour qu'un graphes soit β₀-point critiques ainsi qu'une caractérisation de quelques graphes β₀-point critiques, à savoir les arbres et les graphes sans K1,3. Concernant le nombre de domination stable, nous conjecturons que la classe des arbres i-point critique est équivalente à la classe des graphes i-excellent. Enfin, on caractérise par construction les arbres ayant le nombre de domination par contraction Ctγ(T)=3 et on montre qu'il existe des graphes ayant un nombre de domination stable par contraction très grand.