Gathering synchronous robots in graphs: from general properties to dense and symmetric topologies

The Gathering task by means of a swarm of robots disposed on the vertices of a graph requires robots to move toward a common vertex from where they do not move anymore. When dealing with very weak robots in terms of capabilities, considering synchronous or asynchronous settings may heavily affect the feasibility of the problem. In fact, even though dealing with asynchronous robots in general requires more sophisticated strategies with respect to the synchronous counterpart, sometimes it comes out that asynchronous robots simply cannot solve the problem whereas synchronous robots can. We study general properties of graphs that can be exploited in order to accomplish the gathering task in the synchronous setting, obtaining an interesting sufficient condition for the feasibility, applicable to any topology. We then consider dense and symmetric graphs like complete and complete bipartite graphs where asynchronous robots cannot solve much. In such topologies we fully characterize the solvability of the gathering task in the synchronous setting by suitably combining some strategies arising by the general approach with specific techniques dictated by the considered topologies.