Completely mobile robots in graphs with a resolving property
Abstract
This work extends the study of mobile resolvability in connected graphs by introducing completely mobile resolving sets. As with mobile resolving sets, we consider stationing a collection of robots at the vertices in a resolving set of a graph. Robots may move one at a time to any adjacent vertex as long as set of occupied vertices remains a resolving set. In this new variant, we ask that every robot can traverse every vertex in the graph through a sequence of permitted moves. Graphs possessing at least one completely mobile resolving set are termed mobile-resolvable. We completely characterise the non-mobile-resolvable graphs as paths of order at least three and subdivided stars with three or more leaves and at most two subdivided edges. For trees, we explicitly determine the completely mobile metric dimension, showing that it exceeds the classical metric dimension by one for most mobile-resolvable trees, and by two for certain subdivided stars. Furthermore, we evaluate this parameter across fundamental graph classes-including cycles, complete bipartite graphs, grid graphs, and circulant graphs.
Related
- Hybrid path planning for mobile robots in complex environments: Fusing improved BI-RRT and enhanced DWA
- On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
- Resolving a Problem of Lv and Koolen on the Smallest Eigenvalue of Distance-Regular Graphs
- Minimal Resolving Sets in Rectangular Grid Graphs: A Complete Characterization and Enumeration
- Solid-Resolving Sets on Directed Graphs
BibTeX
@misc{moreno2026completely,
title = {{Completely mobile robots in graphs with a resolving property}},
author = {Jose C. Camacho Moreno and Dorota Kuziak and Ethan Shallcross and James Tuite and Ismael G. Yero},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13339},
eprint = {2610.13339},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13339},
}
RIS
TY - UNPB
TI - Completely mobile robots in graphs with a resolving property
AU - Jose C. Camacho Moreno
AU - Dorota Kuziak
AU - Ethan Shallcross
AU - James Tuite
AU - Ismael G. Yero
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13339
UR - https://arxiv.org/abs/2610.13339
AB - This work extends the study of mobile resolvability in connected graphs by introducing completely mobile resolving sets. As with mobile resolving sets, we consider stationing a collection of robots at the vertices in a resolving set of a graph. Robots may move one at a time to any adjacent vertex as long as set of occupied vertices remains a resolving set. In this new variant, we ask that every robot can traverse every vertex in the graph through a sequence of permitted moves. Graphs possessing at least one completely mobile resolving set are termed mobile-resolvable. We completely characterise the non-mobile-resolvable graphs as paths of order at least three and subdivided stars with three or more leaves and at most two subdivided edges. For trees, we explicitly determine the completely mobile metric dimension, showing that it exceeds the classical metric dimension by one for most mobile-resolvable trees, and by two for certain subdivided stars. Furthermore, we evaluate this parameter across fundamental graph classes-including cycles, complete bipartite graphs, grid graphs, and circulant graphs.
ER -