4 papers
Patrolling cop vs omniscient robber
Nina Chiarelli, Paul Dorbec, MiloÅ¡ StojakoviÄ +1
We study a variant of the classical Cops and Robbers game with one cop and one robber. The cop follows a fixed walk on the graph, called a patrol, that is chosen before the game be…
Cayley trees and increasing 1,2-trees: let's twist!
Julien Courtiel, Matthieu Dien, Paul Dorbec
An increasing 1,2-tree is a labeled graph formed by starting with a vertex and then repeatedly attaching a leaf to a vertex or a triangle to an edge, the labeling of the vertices c…
The 1/3-conjectures for domination in cubic graphs
Paul Dorbec, Michael Antony Henning
A set S of vertices in a graph G is a dominating set of G if every vertex not in S is adjacent to a vertex in S . The domination number of G, denoted by (G), is the minimum car…
Theoretical analysis of git bisect
Julien Courtiel, Paul Dorbec, Romain Lecoq
In this paper, we consider the problem of finding a regression in a version control system (VCS), such as git. The set of versions is modelled by a Directed Acyclic Graph (DAG) whe…