Ensembles localisants et dominants dans les digraphes

lundi 11 Février 2019, 14h, en salle A (2ième étage).

Aline Parreau (LIRIS, Lyon, France)

Abstract :

Un ensemble de sommets S d’un (di)graphe est un ensemble localisant si tous les sommets hors de S ont des voisinages distincts dans S. Le théorème de Ore dit que tout graphe (non orienté) connexe d’ordre n a un ensemble dominant de taille n/2.

Ce théorème reste-t-il vrai si l’ensemble est de plus localisant ?

Cela est conjecturé par Garijo, Gonzlez et Marquez pour les graphes non orientés sans jumeaux. Nous montrons que cela est vrai pour tous les tournois et les graphes acycliques sans jumeaux. Nous donnons de plus une construction d’un ensemble localisant et dominant de taille 4n/5 que tout digraphe sans jumeaux (3n/4 s’il n’y a de plus pas de "quasi-jumeaux") et exhibons de tel graphes qui ont besoin d’au moins 2n/3 sommets.

Travail en collaboration avec Florent Foucaud et Shahrzad Heydarshahi.