Zobrazeno 1 - 10
of 167
pro vyhledávání: '"Parreau, Aline"'
The Maker-Breaker domination game is a positional game played on a graph by two players called Dominator and Staller. The players alternately select a vertex of the graph that has not yet been chosen. Dominator wins if at some point the vertices she
Externí odkaz:
http://arxiv.org/abs/2406.15165
Autor:
Bagan, Guillaume, Duchêne, Eric, Galliot, Florian, Gledel, Valentin, Mikalački, Mirjana, Oijid, Nacim, Parreau, Aline, Stojaković, Miloš
We propose a generalization of positional games, supplementing them with a restriction on the order in which the elements of the board are allowed to be claimed. We introduce poset positional games, which are positional games with an additional struc
Externí odkaz:
http://arxiv.org/abs/2404.07700
We study the Maker-Maker version of the domination game introduced in 2018 by Duch\^ene et al. Given a graph, two players alternately claim vertices. The first player to claim a dominating set of the graph wins. As the Maker-Breaker version, this gam
Externí odkaz:
http://arxiv.org/abs/2306.05728
The metric dimension has been introduced independently by Harary, Melter and Slater in 1975 to identify vertices of a graph G using its distances to a subset of vertices of G. A resolving set X of a graph G is a subset of vertices such that, for ever
Externí odkaz:
http://arxiv.org/abs/2303.10646
Autor:
Duchêne, Eric, Gledel, Valentin, Inerney, Fionn Mc, Nisse, Nicolas, Oijid, Nacim, Parreau, Aline, Stojaković, Miloš
We initiate the study of the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the $H$-game. Maker wins if she claims the edges of a perfect matching in the first
Externí odkaz:
http://arxiv.org/abs/2302.10972
Publikováno v:
European Journal of Combinatorics 115:103772, 2024
We give essentially tight bounds for, $\nu(d,k)$, the maximum number of distinct neighbourhoods on a set $X$ of $k$ vertices in a graph with twin-width at most~$d$. Using the celebrated Marcus-Tardos theorem, two independent works [Bonnet et al., Alg
Externí odkaz:
http://arxiv.org/abs/2301.04217
Autor:
Bagan, Guillaume, Deschamps, Quentin, Duchêne, Eric, Durain, Bastien, Effantin, Brice, Gledel, Valentin, Oijid, Nacim, Parreau, Aline
Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker
Externí odkaz:
http://arxiv.org/abs/2211.01083
The game INFLUENCE is a scoring combinatorial game that has been introduced in 2020 by Duchene et al. It is a good representative of Milnor's universe of scoring games, i.e. games where it is never interesting for a player to miss his turn. New gener
Externí odkaz:
http://arxiv.org/abs/2206.06118
Autor:
Bagan, Guillaume, Deschamps, Quentin, Duchêne, Eric, Durain, Bastien, Effantin, Brice, Gledel, Valentin, Oijid, Nacim, Parreau, Aline
Publikováno v:
In Discrete Mathematics August 2024 347(8)
A locating-dominating set in an undirected graph is a subset of vertices $S$ such that $S$ is dominating and for every $u,v \notin S$, we have $N(u)\cap S\ne N(v)\cap S$. In this paper, we consider the oriented version of the problem. A locating-domi
Externí odkaz:
http://arxiv.org/abs/2112.01910