Les GT se tiennent chaque vendredi de 14h à 15h en salle 178. Vous êtes invités à venir 10 minutes avant pour partager thé, café et gâteaux.

Pour vous inscrire à la liste de diffusion, il suffit d'envoyer un mail à sympa@diff.u-bordeaux.fr avec pour sujet "subscribe labri.go-gt Cookie Monster", où Cookie est remplacé par votre prénom et Monster par votre nom.

Prochains exposés :

Vendredi 25 janvier 2019 - Eternal domination in graphs - Ben Seamone (Dawson College, Canada).

Given a graph, how can one distribute resources to the vertices (nodes) so that one can use these resources to respond to any infinite sequences of demands? This is the fundamental question which the study of eternal domination in graphs attempts to answer. I will give a brief survey of what is known about eternal domination, followed by recent progress on some eternal domination problems. Notably, we refute a conjecture of Klostermeyer and Mynhardt on eternal domination in prisms over graphs, and introduce a fractional version of eternal domination which to our knowledge has not yet been studied. These results were jointly obtained with D. Khatri, A. Krim-Yee, N. Kumar, G. MacGillivray, V. Virgile, and A. Xu.

Vendredi 1 février 2019 - Octal games on graphs - Antoine Dailly (G-SCOP, Grenoble).

Octal games are two-player take-away games played on heaps of counters: the players remove counters from a heap, and may split the heap in two nonempty heaps, under conditions that can be expressed as an octal code. The main question in the study of those games is whether the sequences of their Grundy values (equivalence classes for games, that fully express the winner of the game) on heaps of increasing size are regular. We propose a generalization of those games on graphs: players now remove connected components from a graph, and may disconnect the graph under conditions similar to those of octal games. This definition includes several vertex-deletion games on graphs, such as Arc-Kayles. We focus our study on subtraction games, a subclass of octal games where the players are not allowed to disconnect the graph.

In this talk, I will first give an introduction to the theory of take-away games, before showing how we generalized octal games to play them on graphs, and how we redefined the notion of regularity to study them. I will then give several regularity results for subtraction games on graphs, with a focus on the class of subdivided stars. In particular, we show that all subtraction games on graphs have ultimately periodic sequences of Grundy values. However, we notice that the study of specific families of subtraction games is difficult, even on subdivided stars. Finally, I will show how we used a pseudo-sum of games to study the case of subdivided bistars for the subtraction game CSG(1,2).

The results presented in this talk were jointly obtained with L. Beaudou, P. Coupechoux, S. Gravier, J. Moncel, A. Parreau and É. Sopena.


Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar