92 citations · 359 across the 37 of their papers we have counts for
4 papers · 1 filter
The Maker-Maker domination game in forests
Eric Duchêne, Arthur Dumas, Nacim Oijid +2
We study the Maker-Maker version of the domination game introduced in 2018 by Duchêne et al. Given a graph, two players alternately claim vertices. The first player to claim a domi…
Metric dimension parameterized by treewidth in chordal graphs
Nicolas Bousquet, Quentin Deschamps, Aline Parreau
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 re…
Complexity of Maker-Breaker Games on Edge Sets of Graphs
Eric Duchêne, Valentin Gledel, Fionn Mc Inerney +4
We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the -game. Maker wins if s…
Neighbourhood complexity of graphs of bounded twin-width
Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä +1
We give essentially tight bounds for, , the maximum number of distinct neighbourhoods on a set of vertices in a graph with twin-width at most~. Using the celebra…