Nombre de bondage des graphes triangulés
Valentin Bouquet  1@  
1 : Centre d'études et de recherche en informatique et communications
Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise : EA4629, Conservatoire National des Arts et Métiers [CNAM] : EA4629

Soit G = (S, A) un graphe connexe simple et non orienté. Un ensemble de sommets S ⊆ V est
un dominant de G si pour tout sommet v ∈ V , N [v] ∩ S ̸= ∅. Un ensemble dominant minimum
est un ensemble dominant de cardinalité minimale. La cardinalité d'un tel ensemble dominant
est appelé nombre de domination et est noté γ(G). Le nombre de bondage b(G) est le
nombre minimum d'arêtes dont la suppression dans G augmente le nombre de domination, i.e.
A′ ⊆ A tel que γ(G−A′ ) = γ(G)+1. Nous nous intéressons au nombre de bondage des graphes
triangulés, qui sont les graphes pour lesquels les cycles induits sont de longueurs au plus trois.
Nous montrons que pour les graphes triangulés, le nombre de bondage est au plus la taille d'une
clique maximum ω(G).

 


Personnes connectées : 2 Vie privée
Chargement...