Graphes sans griffe et sans chemin de taille huit

Nous introduisons la notion de dominant. Un ensemble dominant d’un graphe G = (V, E) est un sous-ensemble S ⊆ V tel que chaque sommet v ∈ V \ S a un voisin dans S. Pour faire court, un ensemble dominant est aussi appel´ dominant quand le contexte ne permet aucune ambigu¨ıté. Les

´ ⊆ ∈ sommets de S sont des sommets dominants. Etant donné un ensemble S V , un sommet u V est dit dominé si il a un voisin dans S, et S est un dominant du sous-graphe induit par les sommets de N[S]. Donc S ⊆ V est un dominant de G si tout sommet de V \ S est dominé ou V = S.

Nous pouvons observer que tout graphe poss`ede un dominant puisque l’ensemble des sommets d’un graphe est un dominant de celui-ci. Il est donc naturel de se poser la question suivante : quelle est la cardinalité d’un ensemble dominant minimum d’un graphe ? La cardinalité d’un tel dominant pour un graphe G est appel´ nombre de domination et est noté γ(G). La Figure 1.3 est un exemple de dominant minimum d’un graphe.

O. Ore [66] a montré des conditions nécessaires et suffisantes d’un dominant minimal (au sens de l’inclusion). Notons qu’un dominant minimum est un dominant minimal. Nous avons choisi de réécrire l’énonc´ de son théor`eme pour exprimer des conditions nécessaires, mais non-suffisantes, d’un dominant minimum (et non minimal), comme suit :

Théor`eme 1.3 (O. Ore [66]) Si S est un dominant minimum, alors pour tout sommet v ∈ S :

(a) v n’est voisin d’aucun sommet de S ; ou

(b) il existe un sommet u ∈ V \ S tel que N(u) ∩ S = {v}.

Etant donné un sous-ensemble de sommets S de G, si un sommet u est tel que décrit au point (b) (i.e. N(u) ∩ S = {v}), alors on dit que u est un voisin privé de v relativement `a S. On désigne par pn[v, S] l’ensemble des voisins privés de v par rapport `a S, i.e. pn[v, S] = {u | N[u] ∩ S = {v}}. Donc pour tout ensemble dominant minimum S de G, et pour tout sommet v ∈ S, nous avons pn[v, S] ̸= ∅.

Des variantes de l’ensemble dominant ont eté etudiées. Il s’agit essentiellement de rajouter des contraintes sur l’ensemble dominant, par exemple : l’ensemble dominant doit former un stable, le sous-graphe induit par l’ensemble dominant doit ˆetre connexe, l’ensemble dominant doit dominer tous les sommets du graphe (i.e. les sommets dominants doivent aussi ˆetre dominés), chaque sommet doit ˆetre dominé par exactement un sommet dans l’ensemble dominant.

Pour une vue plus générale de la domination et de ses variantes, nous référons aux livres de T.

Haynes, S. Hedetniemi, et P. Slater [45], [46].

Nous ne donnerons pas ici les définitions précises et techniques de la théorie de la complexit´. Nous référons au livre de M. Garey et D. Johnson [42], au livre de S. Arora et B. Barak [3] pour une version plus modernisée, ainsi qu’`a la th`ese de B. Escoffier [32] qui contient une introduction riche (en fran¸cais) sur la théorie de la complexit´.

Dans cette th`ese, nous serons principalement intéressés par des probl`emes de décision, i.e. des probl`emes pour lesquels la réponse est soit « oui », soit « non ». La classe NP regroupe l’ensemble des probl`emes de décision pour lesquels il existe un algorithme pouvant s’exécuter en temps polynomial (certificat) afin de vérifier si une solution donnée est une réponse positive au probl`eme. La classe P regroupe l’ensemble des probl`emes qui peuvent ˆetre résolus systématiquement, i.e. peu importe l’instance (c.a`.d. les données ou les entrées) du probl`eme, par un algorithme déterministe en temps polynomial. Remarquons que si un probl`eme appartient a` P, alors il appartient aussi a` NP. Malheu-reusement, il existe des probl`emes de décision pour lesquels on ne connaˆıt pas d’algorithme ayant un temps d’exécution polynomial (algorithme polynomial). C’est d’ailleurs le cas du probl`eme suivant :

Satisfiabilite´ (Sat)

Etant donné : une formule booléenne f.

Décider : est-ce que f est satisfiable ?

Expliquons d’abord ce qu’est une formule booléenne. Une variable booléenne peut prendre soit comme valeur ‘0’, ‘fausse’, ou ‘négative’, soit comme valeur ‘1’, ‘vraie’, ou ‘positive’. Une formule booléenne est une combinaison de variables booléennes avec les opérateurs ‘non’, ‘ou’, ‘et’. Une formule est satisfiable si il existe une affectation des variables pour laquelle la formule est ‘vraie’. Le probl`eme Sat pose donc la question de savoir si une formule booléenne donnée est satisfiable ou non. Notons qu’il existe un algorithme polynomial afin de vérifier si une affectation des variables satisfait une formule donnée, et que donc Sat est dans NP. Il est donc naturel de se poser la question suivante : existe-t-il un algorithme polynomial afin de résoudre Sat, dit autrement, est-ce que Sat est dans P ? Mˆeme si on ne connaˆıt toujours pas la réponse a` cette question, il est conjectur´ que Sat fait partie de ses probl`emes dans NP dont on pense qu’ils sont « difficiles » a` résoudre. Par cela, on veut dire qu’il existe des probl`emes dans NP dont on pense qu’ils ne peuvent ˆetre résolus en temps polynomial avec un algorithme déterministe. Ces probl`emes sont considérés comme étant les plus « difficiles » de la classe NP. La classe NP-complet regroupe l’ensemble de ces probl`emes, et Sat a eté le premier probl`eme dont on a démontr´ qu’il était NP-complet, c.f. S. Cook [27] et L. Levin [59].

Pour montrer qu’un probl`eme est dans P, il suffitde donner un algorithme polynomial afin de le résoudre. Qu’en est-il pour montrer qu’un probl`eme Π est NP-complet ? La classe NP-complet a et´ définie comme la classe regroupant les probl`emes les plus difficiles a` résoudre de la classe NP. Il faut donc montrer qu’il existe un algorithme polynomial pour vérifier qu’une solution donnée apporte une réponse positive au probl`eme Π. Il faut aussi montrer que Π est au moins aussi difficile, en pire cas, que les probl`emes NP-complets. Pour cela, on peut faire appel au concept de réduction polynomiale.

Etant donné deux probl`emes et , on dit que se réduit en temps polynomial vers si il existe un algorithme polynomial qui transforme toute instance I de P en une instance I′ de P′, et que les solutions de I et I′ sont équivalentes. Observons que si P peut ˆetre résolu en temps polynomial, alors P′ également. La preuve du Théor`eme 2.1 au Chapitre 2 est un exemple « simple » de réduction polynomiale.

Dans cette th`ese, tous les probl`emes de décision que nous étudions n’appartiennent sans doute pas `a la classe NP. Néanmoins, nous montrerons que ces probl`emes admettent une réduction polynomiale depuis des probl`emes NP-complets. Ces probl`emes sont donc considérés comme au moins aussi difficiles et appartiennent `a la classe des probl`emes NP-difficiles.

Nous finissons cette section en donnant deux probl`emes de graphes notables qui sont NP-complets, et qui nous seront utiles dans cette th`ese.

Stable Maximum (Maximum Independent Set)

Nous avons précédemment remarqués qu’étant donné un stable maximum S d’un graphe G, l’en-semble des sommets qui ne sont pas dans le stable, i.e. V (G) \ S forme une couverture de sommets. Ainsi Stable Maximum est lié au probl`eme de Couverture De Sommets enonc´ ci-dessous.

Couverture De Sommets (Vertex Cover)

Etant donné :

Décider :

un graphe G = (V, E) et un entier positif k.

y a-t-il C ⊆ V , |C| ≤ k, tel que toute arˆete de G a une extrémit´ dans C ?

Couveture De Sommets a et´ montré comme étant NP-complet avec une réduction depuis 3-Sat (une variante de Sat), c.f. [42]. Comme la taille d’un stable maximum est étroitement liée a` la taille d’une couverture de sommets, nous pouvons en déduire que Stable Maximum est aussi NP-complet.

Nous montrons dans cette section que Dominant Minimum peut ˆetre résolu en temps polynomial dans les graphes sans griffe et sans P8.

Important : cette section est l’unique passage de la th`ese o`u la définition du voisinage ouvert d’un

´ ⊆ V , nous ensemble de sommets est lég`erement altérée. Etant donné un ensemble de sommets A⋃  désignons le voisinage ouvert de A comme NG(A) = v∈A NG(v). Ainsi le voisinage ouvert de A peut contenir des sommets de A, mais pas nécessairement tous comme avec le voisinage ferm´.

Nous donnons deux propriétés qui nous permettent de simplifier les graphes sans griffe et sans Pk, pour n’importe quel k fixé, a` considérer afin de résoudre Dominant Minimum.

Propriét´ 2.2 Soit G un graphe. Si u, v sont deux sommets tels que N[u] = N[v], alors γ(G) = γ(G/uv).

Preuve: Soit u′ le sommet de G/uv résultant de la contraction de uv. Soit Γ un ensemble dominant minimum de G. Si u, v ∈ Γ, alors Γ \{v} est un autre dominant de G, une contradiction. Si u ∈ Γ, alors nous prenons Γ′ = (Γ \ {u}) ∪ {u′}. Si u, v ̸∈Γ, alors nous prenons Γ′ = Γ. Dans les deux cas, Γ′ est un dominant de G/uv, et donc γ(G) = |Γ′| ≥ γ(G/uv). Maintenant supposons que γ(G) > γ(G/uv). Soit Γ′ un ensemble dominant minimum de G/uv. Si u′ ∈ Γ′, alors (Γ′ \ {u′}) ∪ {u} est un dominant de G  tel que|(Γ′\ {u′})∪ {u}|= γ(G/uv) < γ(G), une contradiction. Si u′̸∈ Γ′, alors Γ′ est un dominant de G, une contradiction. Donc γ(G) = γ(G/uv). □

Propriét´ 2.3 Soit G = (V, E) un graphe connexe sans griffe tel que δ(G) = 1. Soit u une feuille et v son voisin. Alors il existe Γ un ensemble dominant minimum de G tel que Γ = {v} ∪ Γ′, o`u Γ′ est un ensemble dominant minimum de G′ = G − N[v].

Preuve:  Puisque u est une feuille, il existe Γ un ensemble dominant minimum de G o`u v ∈ Γ. Soit

w ∈ N(v) \ {u}. Puisque G est sans griffe, alors N(w) \ N[v] est une clique. Nous pouvons supposer que w ̸∈Γ, car nous pourrions remplacer w par w′ ∈ N(w) \ N[v] afin d’obtenir un autre ensemble dominant minimum de G (notons que si N(w)\N[v] est vide, alors Γ ne peut ˆetre un ensemble dominant minimum). Nous montrons que Γ′ = Γ \ N[v] est un ensemble dominant minimum de G′ = G − N[v]. Clairement Γ′ est un dominant de G′. Si il existe S un ensemble dominant minimum de G′ tel que |S| < |Γ′|, alors S ∪ {v} est un dominant de G o`u |S ∪ {v}| < Γ, une contradiction. □

En conséquence de la propriét´ précédente, si un ensemble dominant minimum de G′ = G − N[v] peut ˆetre calculé en temps polynomial, alors un ensemble dominant minimum de G peut aussi ˆetre calculé en temps polynomial.

Nous observons que si un graphe poss`ede des structures dominantes de taille fixée, alors nous pouvons calculer un ensemble dominant minimum en temps polynomial dans ce graphe.

Propriét´ 2.4 Soit k > 0 un entier positif fixé et un graphe G = (V, E). Si il existe T ⊆ V , o`u |T | ≤ k et V = N[T ], alors on peut calculer un ensemble dominant minimum dans G en temps polynomial. Preuve: Puisque γ(G) ≤ k + k′, alors nous pouvons calculer un ensemble dominant minimum en O(nk).

Propriét´ 2.5 Soit k, k′ > 0 deux entiers positifs fixés et G = (V, E) un graphe. Si il existe T ⊂ V , o`u |T | ≤ k et W = V \ N[T ] tel que |W | ≤ k′, alors on peut calculer un ensemble dominant minimum dans G en temps polynomial.

Preuve: Puisque γ(G) ≤ k, alors nous pouvons calculer un ensemble dominant minimum en O(nk+k′ ). □

Nous donnons deux lemmes qui nous permettent de conclure que Dominant Minimum peut ˆetre résolu en temps polynomial dans les graphes sans griffe et sans Pk, k ≤ 8, lorsqu’ils contiennent un long cycle induit.

Lemme 2.6 Pour tout entier fixé k ≥ 6, si G est un graphe connexe sans griffe et sans Pk tel que Ck ⊆i G, alors un ensemble dominant minimum de G peut ˆetre calculé en temps polynomial.
Preuve:  Soit Ck = v1 − • • • − vk − v1, Ck ⊆i G. Soit v ̸∈V (Ck) tel que N(v) ∩ V (Ck) ̸= ∅. Puisque G est sans griffe et que k ≥ 6, nous avons 2 ≤ |N(v) ∩ V (Ck)| ≤ 4. Si |N(v) ∩ V (Ck)| = 2, alors les deux voisins de v dans Ck doivent ˆetre consécutifs, et donc Pk ⊆i G, une contradiction. Pour 3 ≤ |N(v) ∩ V (Ck)| ≤ 4, soit w un voisin de v. Si N(w) ∩ V (Ck) = ∅, alors il y a une griffe induite centrée sur v, une contradiction. Donc tous les voisins de v ont un voisin dans Ck, et donc N[Ck] = V . D’apr`es la Propriét´ 2.4, nous pouvons calculer un ensemble dominant minimum de G en temps polynomial. □

Lemme 2.7 Pour tout entier fixé k ≥ 6, si G est un graphe connexe sans griffe, sans Pk et sans Ck tel que Ck−1 ⊆i G, alors un ensemble dominant minimum de G peut ˆetre calculé en temps polynomial.

Preuve: Soit Ck−1 = v1 − • • • − vk−1 − v1, Ck−1 ⊆i G, et v ̸∈V (Ck−1) tel que N(v) ∩ V (Ck−1) ̸= ∅. Si k ≥ 7, alors 2 ≤ |N(v) ∩ V (Ck−1)| ≤ 4 ; si k = 6, alors 2 ≤ |N(v) ∩ V (Ck−1)| ≤ 5. Soit w un voisin de v tel que N(w) ∩ V (Ck−1) = ∅. Si 3 ≤ |N(v) ∩ V (Ck−1)| ≤ 5, alors il y a une griffe induite centrée sur v, une contradiction. Si |N(v) ∩ V (Ck−1)| = 2, alors il y a Pk ⊆i G, une contradiction. Donc N[Ck−1] = V et d’apr`es la Propriét´ 2.4, nous pouvons calculer un ensemble dominant minimum de

G en temps polynomial. □

Dans cette section, nous montrons que, pour tout entier positif fixé k ≤ 8, si G est un graphe sans (griffe, Pk, Ck, Ck−1), tel que Ck−2 ⊆i G, alors un ensemble dominant minimum de G peut ˆetre calculé en temps polynomial. Le premier lemme donne une propriét´ structurelle de G. Nous utilisons cette propriét´ pour montrer deux autres lemmes, le premier étant pour k = 6, et le second pour 7 ≤ k ≤ 8.

Lemme 2.8 Pour tout entier positif fixé k ≥ 6, si G est un graphe connexe sans (griffe,Pk, Ck, Ck−1) tel que Ck−2 ⊆i G, alors W = V \ N[V (Ck−2)] est un ensemble indépendant de G.

Preuve: Soit C = Ck−2 = v1 − • • • − vk−2 − v1, o`u C ⊆i G, et soit v ∈ N[V (C)] \ V (C). Nous avons 2 ≤ |NC (v)| ≤ 5 (notons que |NC (v)| = 5 seulement si C = C5). Soit W = V \ N[V (C)], et soit w ∈ W un voisin de v. Si 3 ≤ |NC (v)| ≤ 5, alors il y a une griffe, une contradiction. Donc v est tel que NC (v) = {vi, vi+1 }, pour 1 ≤ i ≤ k − 2 (par abus de notation, quand i = k − 2 nous supposons que vi+1 = v1). D’apr`es la Propriét´ 2.2, nous pouvons supposer que tous les sommets contractables de G sont contractés. De plus, d’apr`es la Propriét´ 2.3, nous pouvons supposer que G n’a pas de feuille.

Supposons, par contradiction, que w ait un voisin w′, o`u w′ ∈ W . Si w′ n’a pas de voisin dans N(V (C)), alors il y a Pk ⊆i G, une contradiction. Donc w′ a un voisin dans N(V (C)). Rappelons que N[w] ̸= N[w′]. Si vw′ ̸∈E, alors il y a Pk ⊆i G, une contradiction. Donc w et w′ ont les mˆemes voisins dans N(V (C)) mais pas dans W . Donc il existe r ∈ W tel que rw ∈ E, rw′ ̸∈E. Les arguments précédents impliquent que rv ∈ E. Mais G[{r, v, vi, w′}] est une griffe, une contradiction.

Donc, W = V \ N[V (Ck−2)] est un ensemble indépendant de G. □

Lemme 2.9 Si G est un graphe connexe sans (griffe,P6, C6, C5) tel que C4 ⊆i G, alors un ensemble dominant minimum de G peut ˆetre calculé en temps polynomial.

Preuve: Soit C = C4 = v1 − • • • − v4 − v1, o`u C ⊆i G, et soit v ̸∈V (C) tel que N(v) ∩ V (C) ̸= ∅. Nous avons 2 ≤ |NC (v)| ≤ 4. Soit W = V \ N[C], et soit w ∈ W un voisin de v. Si 3 ≤ |NC (v)| ≤ 4, alors G poss`ede une griffe, une contradiction. Donc NC (v) = {vi, vi+1 }, pour 1 ≤ i ≤ 4 (par abus de notation, quand i = 4 nous supposons que vi+1 = v1). D’apr`es la Propriét´ 2.2, nous pouvons supposer que tous les sommets contractables de G sont contractés. De plus, d’apr`es la Propriét´ 2.3, nous pouvons supposer que G n’a pas de feuille.

D’apr`es la Propriét´ 2.5, si |W | ≤ 1, alors un ensemble dominant minimum de G peut ˆetre calculé en temps polynomial. Donc nous pouvons supposer que |W | ≥ 2. D’apr`es le Lemme 2.8, W est un ensemble indépendant de G. Nous montrons que tous les sommets v ∈ N[W ] \ W ont exactement le mˆeme voisinage dans C.

Soit w, w′ ∈ W , w ̸= w′, tels que w a un voisin v ∈ N[C] \ V (C) et w′ a un voisin v′ ∈ N[C] \ V (C). Puisque G est sans griffe v ̸= v′. Sans perte de généralit´ NC (v) = {v1, v2}. Supposons que NC (v) ̸= NC (v′). Sans perte de généralit´ NC (v′) = {v2, v3 } (notons que NC (v′) = {v1, v4} est symétrique). Si vv′ ̸∈E, alors w − v − v1 − v4 − v3 − v′ = P6, sinon v1 − v − v′ − v3 − v4 = C5, une contradiction. Maintenant il reste le cas NC (v′) = {v3, v4}. Nous avons vv ′ ̸∈E sinon il y a une griffe, mais w −v −v1 −v4 −v′ −w′ = P6, une contradiction. Alors, sans perte de généralité, tous les sommets w ∈ W n’ont que des voisins v ∈ N[C] \ V (C) tel que N(v) = {v1, v2}.

Soit |W | = q, o`u q ≥ 2. Nous montrons que γ(G) = q + 1. Puisque W est un ensemble indépendant, et que pour toute paire w, w′ ∈ W , w ̸= w′, nous avons N[w] ∩ N[w′] = ∅, nous devons prendre q sommets de N[W ] pour dominer les sommets W . Ces sommets ne peuvent dominer ni v3 ni v4. Donc γ (G) ≥ q + 1.

Nous construisons un ensemble dominant minimum de G. Nous prenons un voisin de chaque w ∈ W pour former R. Clairement, Γ = R∪{v3} domine V (C)∪N[R]. Supposons qu’il existe s ∈ N[C]\V (C) qui n’est pas dominé par Γ. Si NC (s) = {v1, v2}, alors il existe r ∈ R tel que G[{r, s, v1, v4}] est une griffe, une contradiction. Si NC (s) = {v1, v4}, alors w − v − v2 − v3 − v4 − s = P6, une contradiction. Si NC (s) = {v1, v2, v4}, alors il existe r ∈ R tel que G[{r, s, v2, v3}] est une griffe, une contradiction. Donc tous les sommets s ̸∈N[R] ∪ V (C) sont dominés par v3. Nous en déduisons que Γ est un ensemble dominant minimum de G. Clairement Γ peut ˆetre construit en temps polynomial. □

Lemme 2.10 Pour k ∈ {7, 8}, si G est un graphe connexe sans (griffe, Pk, Ck, Ck−1) tel que Ck−2 ⊆i G, alors un ensemble dominant minimum de G peut ˆetre calculé en temps polynomial.

Preuve: D’apr`es les Propriétés 2.2 et 2.3, nous pouvons supposer que tous les sommets contrac-tables de G sont contractés et que G n’a pas de feuille. Soit C = Ck−2 = v1 − • • • − vk−2 − v1, C ⊆i G et v ∈ N[C] \ V (C). Nous avons 2 ≤ |NC (v)| ≤ 5 (notons que |NC (v)| = 5 seulement si C = C5). Soit S = N[C] \ V (C), W = V \ N[C] et w ∈ W un voisin de v. Si 3 ≤ |NC (v)| ≤ 4, alors G a une griffe, une contradiction. Donc, v est tel que NC (v) = {vi, vi+1}, pour 1 ≤ i ≤ k − 2 (par abus de notation, quand i = k − 2 nous supposons que vi+1 = v1).

w Nous montrons que pour tous w ∈ W, il existe v, v′ ∈ N(w) tels que NC (v) ∩ NC (v′) = ∅ . Soit

∈W et v, v′∈NS(w), v = v′.

Premi`erement, nous montrons que NC (v) ̸= NC (v′). Supposons que NC (v) = NC (v′). Sans perte de généralit´ NC (v) = {v1, v2}. Nous avons vv′ ∈ E ou sinon G[{v, v′, v1, vk−2}] est une griffe. Puisque N[v] ̸= N[v′], il existe u ∈ V tel que uv ∈ E et uv′ ̸∈E. Si u ∈ W , alors d’apr`es le Lemme 2.8, nous avons uw ̸∈E, mais G[{u, v, w, v1}] est une griffe, une contradiction. Donc nous pouvons supposer que u ∈ S. Si NC (u) = {v1, v2}, alors G[{u, v′, v2, v3}] est une griffe, une contradiction. Donc NC (u) ̸= NC (v) et nous pouvons supposer que uw ̸∈E, ou sinon nous avons u, v deux voisins de w avec un voisinage distinct dans C. Si NC (u) ∩ NC (v) = ∅, alors G[{u, v, v1, w}] est une griffe, une contradiction. Donc, sans perte de généralité, nous supposons que NC (u)∩NC (v) = {v1}, mais dans ce cas G[{u, v, v2, w}] est une griffe, une contradiction. Donc N[v] = N[v′] et v, v′ peuvent ˆetre contractés, impliquant que w est une feuille, une contradiction. Donc pour tout w ∈ W, il existe v, v′ ∈ NS(w), v ̸= v′ tels que NC (v) ̸= NC (v′).

Nous montrons que NC (v) ∩NC (v′) = ∅. Sans perte de généralité, supposons que NC (v) = {v1, v2} et que NC (v′) = {v2, v3 }. Si vv′ ∈ E, alors v1 − v − v′ − v3 − • • • − vk−2 − v1 = Ck−1, sinon v1 − v − w − v′ − v3 − • • • − vk−2 − v1 = Ck, une contradiction. Donc tous les sommets w ∈ W, ont deux voisins v, v′ ∈ S tels que NC (v) ∩ NC (v′) = ∅.

D’apr`es la Propriét´ 2.5, nous pouvons supposer que |W | ≥ 2. Soit w, w′ ∈ W (rappelons que ww ′ ∈/ E). Puisque w et w′ ont deux voisins dans S qui n’ont pas de voisinage s’intersectant dans C, soit v ∈ N(w), v′ ∈ N(w′) tels que NC (v) ∩ NC (v′) = ∅. Sans perte de généralit´ NC (v) = {v1, v2}. Supposons que NC (v′) = {v3, v4} (notons que N(v′) = {vk−2, vk−3} est symétrique). Si vv′ ∈ E, alors G[{v, v′, v1, w}] est une griffe, sinon w −v −v1 −vk−2 −• • •−v4 −v′ −w′ = Pk, une contradiction. Donc les sommets de NC (v) ne sont pas adjacents aux sommets de NC (v′). Nous en déduisons que pour k = 7, puisque Ck−2 = C5, une telle configuration n’est jamais possible. Nous avons donc |W | ≤ 1 et d’apr`es la Propriét´ 2.5, un ensemble dominant minimum peut ˆetre calculé en temps polynomial.

Nous traitons le cas restant o`u k = 8. Soit |W | = q, q ≥ 2. Nous montrons que γ(G) = q + 2. Puisque W est indépendant et que pour toute paire distincte w, w′ ∈ W , N[w] ∩ N[w′] = ∅, alors nous devons prendre q sommets de N[W ] afin de dominer les sommets de W . Soit w, w′ ∈ W . D’apr`es les arguments précédents, nous pouvons supposer que w a un voisin v tel que NC (v) = {v1, v2}, et que w′ a un voisin v′ tel que NC (v′) = {v4, v5} (chaque sommet de W a deux voisins qui sont respectivement {v1, v2} et {v4, v5} car C = C6). Puisque G est sans griffe, alors vv′ ̸∈E. Les q sommets qui dominent W ne peuvent dominer v3 et v6. Donc γ(G) ≥ q + 1.

Supposons que γ(G) = q + 1. L’ensemble dominant minimum de G doit contenir un sommet s ∈ S qui est un voisin de v3 et v6. Si vs ∈ E, respectivement v′s ∈ E, alors G a une griffe (car s ne peut ˆetre complet a` NC (v) ∪ NC (v′)), une contradiction. Aussi, s doit avoir (v1 ou v5) et (v2 ou v4) comme voisins, sinon G a une griffe. Nous supposons d’abord que N(s) = {v1, v2, v3, v6}. Alors w−v−v1 −s−v3−v4−v′−w′ = P8 (rappelons que vv′ ̸∈E puisque G est sans griffe), une contradiction. Le cas o`u N(s) = {v3, v4, v5, v6} est symétrique. Maintenant nous supposons que N(s) = {v1, v3, v4, v6} (notons que N(s) = {v2, v3, v5, v6} est symétrique). Alors w − v − v2 − v3 − s − v6 − v5 − v′ = P8, une contradiction. Donc γ(G) ≥ q + 2.

Nous montrons que Γ = {v1, v4} ∪ W est un ensemble dominant minimum de G. Clairement Γ domine N[W ] ∪ V (C). Soit s ̸∈N[W ] ∪ V (C). Donc s ∈ S. Supposons que sv1, sv4 ̸∈E. D’apr`es les arguments précédents, nous avons ws ̸∈E et vs ̸∈E, sinon G[{v, s, v1, w}] est une griffe. Si N(s) = {v2, v3}, alors w − v − v1 − v6 − v5 − v4 − v3 − s = P8, une contradiction. Par symétrie N(s) ̸= {v5, v6}. Comme montré précédemment N(s) ̸= {v2, v3, v5, v6}. Donc tous s ̸∈N[W ] ∪ V (C) est dominé par v1 ou v4. Nous en déduisons que Γ = {v1, v4} ∪ W est un ensemble dominant de G. □

D’apr`es les Lemmes 2.6, 2.7, 2.9, 2.10, nous obtenons le corollaire suivant :

Corollaire 2.11 Soit G un graphe connexe sans griffe et sans Pk, o`u 6 ≤ k ≤ 8. Si Cl ⊆i G, o`u k − 2 ≤ l ≤ k, alors un ensemble dominant minimum de G peut ˆetre calculé en temps polynomial.

Dans cette section, nous montrons que Dominant Minimum peut ˆetre résolu en temps polynomial dans les graphes sans griffe et sans P8. En commen¸cant par le résultat sur la complexit´ du Dominant Minimum dans les graphes sans griffe et sans P5, nous montrons successivement que le probl`eme peut ˆetre résolu en temps polynomial dans les graphes sans griffe et sans P6, puis dans les graphes sans griffe et sans P7, et nous concluons sur la classe des graphes sans griffe et sans P8.

D. Malyshev a montré dans [62] que Dominant Minimum peut ˆetre résolu en temps polynomial dans les graphes sans K1,4 et sans P5. Donc nous obtenons le lemme suivant.

Lemme 2.12 Dominant Minimum peut ˆetre résolu en temps polynomial dans les graphes sans griffe et sans P5.

Nous pouvons maintenant montrer le résultat suivant :

Lemme 2.13 Dominant Minimum peut ˆetre résolu en temps polynomial dans les graphes sans griffe et sans P6.

Preuve: D’apr`es le Corollaire 2.11, si Cl ⊆i G, 4 ≤ l ≤ 6, alors on peut calculer un ensemble dominant minimum dans G en temps polynomial. Si G est sans-(griffe,C4, C5, C6, P6), alors G est un graphe triangulé. Or on sait qu’il est possible de calculer un ensemble dominant minimum dans les graphes triangulés sans griffe. □

Lemme 2.14 Si G est un graphe connexe sans (griffe,C5, C6, C7, P7), alors un ensemble dominant minimum de G peut ˆetre calculé en temps polynomial.

Preuve: D’apr`es les Propriétés 2.2 et 2.3, nous pouvons supposer que tous les sommets contractables de G sont contractés et que G n’a pas de feuille. D’apr`es le Lemme 2.13, nous pouvons supposer que P6 ⊆i G. Soit P = v1 − v2 − v3 − v4 − v5 − v6.

Soit W = V \ N[V (P )]. D’apr`es la Propriét´ 2.4, si W = ∅, alors on peut calculer un en-semble dominant minimum de G en temps polynomial. Nous pouvons donc supposer que W ̸= ∅. Soit S = {v ∈ V \ V (P ) : 2 ≤ |NP (v)| ≤ 4}. Nous définissons Si ⊆ S comme les sommets v tels que |NP (v)| = i. Soit Hi = {v ∈ S2 : NP (v) = {vi, vi+1}, 1 ≤ i ≤ 5}. Puisque G est sans griffe, chaque Hi est une clique. Si il y a une arˆete riri+1 ∈ E avec ri ∈ Hi, ri+1 ∈ Hi+1, alors

P = v1 − • • • − vi − ri − ri+1 − vi+2 − • • • − v6 = P7, une contradiction. Si il y a une arˆete rirj ∈ E avec ri ∈ Hi, rj ∈ Hj et j ≥ i + 3, alors Cp ⊆i G, p ≥ 5. Donc H1 est anti-complet a` H2, H4, H5 ; et H2 est anti-complet a` H3, H5 ; et H3 est anti-complet a` H4.

Nous définissons Ri comme l’ensemble des sommets de Hi ayant un voisin dans W , i.e. Ri = {v ∈ Hi : NW (v) ̸= ∅}, pour 1 ≤ i ≤ 5. Puisque G est sans P7, alors R1 = R5 = ∅.

Soit r ∈ Ri, r′ ∈ Ri, r ̸= r′, o`u i ∈ {2, 4}, tels que r, respectivement r′, a un voisin w ∈ W , respectivement w′ ∈ W . Nous montrons que NS(r) = NS(r′).

Supposons, par contradiction, qu’il existe s∈S tel que rs∈E, r′s̸∈ E. D’apr`es les arguments précédents s ̸∈Ri ∪ Hi−1 ∪ Hi+1. Soit i = 2 (le cas i = 4 est symétrique). Rappelons que H2 est anti-complet `a H1, H3, H5, et donc s ∈ H4 ∪ S3 ∪ S4. Si s ∈ H4, alors G[{r, w, v3, s}] est une griffe, une contradiction. Donc s ∈ S3 ∪ S4. Si NP (s) = {v1, v2, v3}, alors G[{r ′, v3, v4, s}] est une griffe, une contradiction. Si NP (s) = {v2, v3, v4}, alors G[{r′, v1, v2, s}] est une griffe, une contradiction. Si NP (s) = {v3, v4, v5} ou NP (s) = {v4, v5, v6}, alors G[{r, v2, w, s}] est une griffe, une contradiction. Donc s ∈ S4. Si NP (s) = {v1, v2, v3, v4}, alors G[{r, v1, v4, s}] est une griffe, une contradiction. Si NP (s) = {v2, v3, v4, v5}, alors G[{r,′ v1, v2, s}] est une griffe, une contradiction. Si NP (s) = {v3, v4, v5, v6}, alors G[{r, v4, v6, s}] est une griffe, une contradiction. Maintenant prenons i = 3. Rappelons que H3 est anti-complet `a H2, H4, et que donc s ∈ H1 ∪ H5 ∪ S3 ∪ S4. Si s ∈ H1 (le cas s ∈ H5 est symétrique), alors G[{r, w, v3, s}] est une griffe, une contradiction. Donc s ∈ S3 ∪ S4. Si NP (s) = {v1, v2, v3} (le cas NP (s) = {v4, v5, v6} est symétrique), alors G[ {r, w, v4, s}] est une griffe, une contradiction. Si NP (s) = {v2, v3, v4} (le cas NP (s) = {v3, v4, v5} est symétrique), alors G[{r′, v4, v5, s}] est une griffe, une contradiction. Donc s ∈ S4. Si NP (s) = {v1, v2, v4, v5} ou NP (s) = {v1, v2, v5, v6}, alors G[{r, v1, v5, s}] est une griffe, une contradiction. Si NP (s) = {v2, v3, v5, v6}, alors G[{r′, v3, v4, s}] est une griffe, une contradiction. Si NP (s) = {v1, v2, v3, v4} (le cas NP (s) = {v3, v4, v5, v6 } est sy-métrique), alors G[{r′, v4, v5, s}] est une griffe, une contradiction. Donc NP (s) = {v2, v3, v4, v5} mais G[{r, v2, v5, s}] est une griffe, une contradiction. Donc NS(r) = NS(r′).

Soit r2 ∈ R2, r2′ ∈ R2, r2 ̸= r2′ tels que r2 a un voisin w ∈ W , et r2′ a un voisin w′ ∈ W . Soit r4 ∈ R4, r4′ ∈ R4, r4 ̸= r4′ tels que r4 est voisin de w, et r4′ est voisin de w′. Nous montrons que NS\H4 (r2) = NS\H4 (r2′), respectivement NS\H2 (r4) = NS\H2 (r4′).

Supposons, par contradiction, qu’il y ait s ∈ S tel que r2s ∈ E, r2′s ̸∈E. D’apr`es les arguments précédents s ̸∈H1 ∪H2 ∪H3. Quand s ∈ H4, nous savons que s n’est pas un voisin de w. Si s ∈ H4 ∪H5, alors G[{r2, v2, w, s}] est une griffe, une contradiction. Donc s ∈ S3 ∪ S4. Si NP (s) = {v1, v2, v3}, alors G[{r2′, v3, v4, s}] est une griffe, une contradiction. Si NP (s) = {v2, v3, v4}, alors G[{r2′, v1, v2, s}] est une griffe, une contradiction. Si NP (s) = {v3, v4, v5}, alors G[{r2, v2, w, s}] est une griffe, une contra-diction. Si NP (s) = {v4, v5, v6}, alors G[{r2, v4, v6, s}] est une griffe, une contradiction. Donc s ∈ S4. Si NP (s) = {v1, v2, v4, v5} ou NP (s) = {v1, v2, v5, v6}, alors G[{r, v1, v5, s}] est une griffe, une contra-diction. Si NP (s) = {v2, v3, v5, v6}, alors G[{r′, v3, v4, s}] est une griffe, une contradiction. Si NP (s) = {v1, v2, v3, v4 }, alors G[{r2, v1, v4, s}] est une griffe, une contradiction. Si NP (s) = {v2, v3, v4, v5}, alors G[{r2′, v1, v2, s}] est une griffe, une contradiction. Si NP (s) = {v3, v4, v5, v6}, alors G[{r2, v4, v6, s}] est une griffe, une contradiction. Donc NS\H4 (r2) = NS\H4 (r 2′) et par symétrie, pour r4′ ∈ R4, r4′ ̸= r4, nous avons NS\H2 (r4) = NS\H2 (r4′).

Soit w ∈ W . Nous montrons que w n’a pas deux voisins ri, ri+1 o`u ri ∈ Ri, ri+1 ∈ Ri+1. Nous supposons, par contradiction, que ces deux voisins existent. Alors v1−• • •−vi −ri −w−ri+1 −vi+2 −• • •− v6 = P8, une contradiction. Maintenant, puisque R1 = R5 = ∅, si w a deux voisins ri ∈ Ri, rj ∈ Rj, i ̸= j, alors ces deux voisins sont r2 ∈ R2, r4 ∈ R4, avec r2r4 ∈ E, sinon w −r4 −v4 −v3 −r2 −w = C5. De plus, quand w a deux voisins r2 ∈ R2, r4 ∈ R4, alors chaque voisin w′ ∈ NW (w) a r2 et r4 comme voisin. Supposons, par contradiction, que w ait un voisin w′ ∈ W tel que w′r2 ̸∈E (le cas w′r4 ̸∈E est symétrique). Alors w′ − w − r2 − v3 − • • • − v6 = P7, une contradiction. Nous en déduisons que N[w] = N[w′], une contradiction.

Donc en définissant Z24 = {w ∈ W : w a deux voisins r2 ∈ R2, r4 ∈ R4}, nous avons Z24 un ensemble indépendant de G.

Soit w, w′ ∈ Z24, w ̸= w′. Puisque G est sans griffe, nous avons N(w) ∩ N(w′) = ∅. Nous montrons que NR2 (w) est anti-complet a` NR4 (w′), et que NR4 (w) est anti-complet a` NR2 (w′). Par contradiction, si w a un voisin r2 ∈ R2, et que w′ a un voisin r4 ∈ R4, tels que r2r4 ∈ E, alors G[{v2, r2, w, r4}] est une griffe, une contradiction.

Soit Zi = {w ∈ W : w a un voisin dans Ri \ (NRi (Z24)}, 2 ≤ i ≤ 4}.

Nous montrons que Z2, Z3, Z4 sont deux a` deux anti-complets. Si il y a une arˆete w2w4 ∈ E, o`u w2 ∈ Z2, w4 ∈ Z4, avec r2′ ∈ R2, r4′ ∈ R4 les voisins respectifs de w2, w4, alors w2−r2′−v3−v4 −r4′−w4− w2 = C6 (r2′r4′ ̸ E sinon G[{v2, r2′, w2, r4′}] est une griffe). Si il y a une arˆete w2w3 ∈ E, o`u w2 ∈ Z2, w3 ∈ Z3, avec r2′ ∈ R2, r3′ ∈ R3 les voisins respectifs de w2, w3, alors w2 − r2′ − v3 − r3′ − w3 − w2 = C5 (rappelons que r2′r3′ ̸ E). Nous en déduisons par symétrie qu’il n’y a pas d’arˆete entre Z3 et Z4.

Soit Y = W \(Z2 ∪Z3 ∪Z4 ∪Z24). Observons que pour tout w ∈ Y , nous avons NZ2 (w) = NZ4 (w) = NZ24 (w) = ∅, sinon P7 ⊆i G.

Soit Y3 = {w ∈ Y : w a un voisin dans Z3}. Si il existe w′ ∈ Y \ Y3 tel que w′ a un voisin w ∈ Y3, alors P7 ⊆i G. Donc Y = Y3.

Nous montrons que nous pouvons supposer que Y3, Z2, Z4 sont trois ensembles indépendants de G. Les arguments sont les mˆemes pour les trois ensembles, donc nous montrons que Z2 est un ensemble indépendant de G. Supposons, par contradiction, qu’il y ait w1, w2 ∈ Z2 tels que w1w2 ∈ E. Nous montrons que NR2 (w1) = NR2 (w2). Si NR2 (w1) ̸= NR2 (w2), alors il existe r2 ∈ R2 qui est un voisin de w1 mais n’est pas un voisin w2. Alors w2 − w1 − r2 − v3 − • • • − v6 = P7, une contradiction. Si NZ2 (w1) ̸= NZ2 (w2), alors il existe w3 ∈ Z2 tel que w2w3 ∈ E, w1w3 ̸ E, mais G[{v2, r2, w1, w3}] est une griffe, une contradiction. Alors N[w1] = N[w2], une contradiction. Donc Z2, Z4, Y3 sont trois ensembles indépendants de G.

Puisque G est sans griffe, alors pour toute paire distincte w1, w2 ∈ Z2 ∪ Z4 ∪ Y3, nous avons N(w1) ∩ N(w2) = ∅.

Nous montrons que pour tout w ∈ Y3, N(w) est une clique. Soit w ∈ Y3. Supposons qu’il y ait s, s′ deux sommets non-adjacents dans N(w). Puisque G est sans griffe, s, s′ n’ont pas de voisin commun dans R3. Soit r ∈ R3 un voisin de s. Alors s′ −w −s−r −v3 −v2 −v1 = P7, une contradiction.

Puisque G est sans griffe, si il y a un sommet r ∈ Ri ayant un voisin z ∈ Zi, et un sommet s ∈ S tel que sz ̸ E et vi ̸ N(s), alors G a une griffe, une contradiction, (notons que vi+1 ̸ N(s) est symétrique). Donc N(Zi) est anti-complet a` Hj, j ̸= i.

Nous montrons que nous pouvons supposer que Z2 = Z4 = ∅. Les arguments sont les mˆemes dans les deux cas, donc nous considérons Z2. Soit r, r′ ∈ R2 deux voisins de w ∈ Z2. Nous mon-trons que N[r] = N[r′]. Puisque NR(w) = NR2 (w) et rr′ ∈ E , alors comme montré précédemment NS(r) = NS(r′). Pour une paire distincte w1, w2 ∈ Z2, N(w1) ∩ N(w2) = ∅. Donc N[r] = N[r′], une contradiction. Alors w est une feuille, une contradiction.