2025/07/22 by Ethan Shallcross, James Tuite, Shallcross, Ethan +6
Engineering · Mathematics · #Control and Dynamics of Mobile Robots #Fixed Point Theorems Analysis
paper · pdf · doi:10.48550/arxiv.2507.16622
The general position problem for graphs asks for the largest number of vertices in a subset S ⊆ V(G) of a graph G such that for any u,v ∈ S and any shortest u,v-path P we have S ∩ V(P) = \ u,v\ , whereas the mutual visibility problem requires only that for any u,v ∈ S there exists a shortest u,v-path with S ∩ V(P) = \ u,v\ . In the mobile versions of these problems, robots must move through the network in general position/mutual visibility such that every vertex is visited by a robot. This paper solves some open problems from the literature. We quantify the effect of adding the restriction that every robot can visit every vertex (the so-called completely mobile variants), prove a bound on both mobile numbers in terms of the clique number, and find the mobile mutual visibility number of line graphs of complete graphs, strong grids and Cartesian grids.