RT journal article
T1 Mobile mutual-visibility sets in graphs
A1 Dettlaff, Magda
A1 Lemanska, Magdalena
A1 Rodríguez Velázquez, Juan A.
A1 González Yero, Ismael
A2 Matemáticas
K1 Mobile mutual-visibility set
K1 mutual-visibility number
K1 total mutual-visibility
AB Given a connected graph G, the mutual-visibility number of G is the cardinality of alargest set S such that for every pair of vertices x, y ∈ S there exists a shortest x, y-pathwhose interior vertices are not contained in S. Assume that a robot is assigned to eachvertex of the set S. At each stage, one robot can move to a neighbouring vertex. Then S isa mobile mutual-visibility set of G if there exists a sequence of moves of the robots suchthat all the vertices of G are visited while maintaining the mutual-visibility property at alltimes. The mobile mutual-visibility number of G, denoted Mobµ(G), is the cardinalityof a largest mobile mutual-visibility set of G. In this paper we introduce the concept ofthe mobile mutual-visibility number of a graph. We begin with some basic properties ofthe mobile mutual-visibility number of G and its relationship with the mutual-visibilitynumber of G. We give exact values of Mobµ(G) for particular classes of graphs, i.e.cycles, wheels, complete bipartite graphs, and block graphs (in particular trees). Moreover, we present bounds for the lexicographic product of two graphs and show characterizationsof the graphs achieving the limit values of some of these bounds. As a consequence of thisstudy, we deduce that the decision problem concerning finding the mobile mutual-visibilitynumber is NP-hard. Finally, we focus our attention on the mobile mutual-visibility numberof line graphs of complete graphs, prism graphs and strong grids of two paths.
PB Society of Mathematicians, Physicists and Astronomers of Slovenia
SN 1855-3974
YR 2025
FD 2025
LK http://hdl.handle.net/10498/39355
UL http://hdl.handle.net/10498/39355
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 09-may-2026