4 papers
Incidence, a Scoring Positional Game on Graphs
Guillaume Bagan, Quentin Deschamps, Eric Duchêne +5
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…
Eternal dominating sets on digraphs and orientations of graphs
Guillaume Bagan, Alice Joffard, Hamamache Kheddouci
We study the eternal dominating number and the m-eternal dominating number on digraphs. We generalize known results on graphs to digraphs. We also consider the problem "oriented (m…
Complexity of Edge Monitoring on Some Graph Classes
Guillaume Bagan, Fairouz Beggas, Mohammed Haddad +1
In this paper, we study the complexity of the edge monitoring problem. A vertex monitors an edge if both extremities together with form a triangle in the graph. Given a…
A Trichotomy for Regular Simple Path Queries on Graphs
Guillaume Bagan, Angela Bonifati, Benoit Groz
Regular path queries (RPQs) select nodes connected by some path in a graph. The edge labels of such a path have to form a word that matches a given regular expression. We investiga…