Roman Domination on Graphings

Abstract

We study a variant of domination, called Roman domination, where we must assign to each vertex one of the labels 0, 1, or 2 and require that every vertex with label 0 has a neighbour with label 2. We study the problem of finding a low-cost Roman dominating function on Lebesgue-measurable graphings, that is, on infinite graphs whose vertices are the points of a probability space. We provide a framework to tackle optimisation problems in the measurable combinatorial setting. In particular, we fully answer the Roman domination problem on irrational cycle graphs, a specific type of graphing on the space $\mathbb{R}/\mathbb{Z}$ where an irrational number $\alpha$ is given and two vertices are adjacent if and only if their distance is $\alpha$.

14 pages