Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane

In this paper we study the computational power of mobile robots without global coordination. A comprehensive evaluation of the computational power of robots moving within the Euclidean plane has been proposed by Das et al. in 2016. In their work, the authors study the relations between classic synchronization models, namely fully-synchronous, semi- synchronous, and asynchronous, and variations of them where robots are endowed with a visible light, i.e. they are luminous. Here we are interested in similar settings but for robots moving on graphs. In particular, we first prove computational relationships among classic models on graphs. To this respect, we investigate the gathering problem and disprove conjectures previously posed in the literature. Second, we compare classic models against luminous models. Third, we highlight the differences among different luminous models. Finally, we compare our results with those holding in the Euclidean plane.