RT journal article
T1 The k-Distance Mutual-Visibility Problem in Graphs
A1 Cera López, Martín
A1 García Vázquez, Pedro
A1 Valenzuela Tripodoro, Juan Carlos
A1 González Yero, Ismael
A2 Matemáticas
K1 k-Distance mutual-visibility number
K1 k-Distance mutual-visibility set
K1 Mutual-visibility
AB The concept of mutual visibility in graphs, introduced recently, addresses a fundamental problem in Graph Theory concerning the identification of the largest set of vertices in a graph such that any two vertices have a shortest path connecting them, excluding internal vertices of the set. Originally motivated by some challenges in Computer Science related to robot navigation, the problem seeks to ensure unobstructed communication channels between navigating entities. The mutual-visibility problem involves determining a largest mutual-visibility set in a graph. The mutual-visibility number of a graph represents the cardinality of the largest mutual-visibility set. This concept has sparked significant research interest, leading to connections with classical combinatorial problems like the Zarankiewicz problem and Turán-type problems. In this paper, we consider practical limitations in network visibility and our investigation extends the original concept to k-distance mutual-visibility. In this case, a pair of vertices is considered S-visible if a shortest path of length at most k exists, excluding internal vertices belonging to the set S. The k-distance mutual-visibility number represents the cardinality of a largest k-distance mutual-visibility set. We initiate the study of this new graph parameter. We prove that the associate decision problem belongs to the NP-complete class. We also give some properties and tight bounds, as well as, the exact value of such parameter for some particular non trivial graph classes.
PB Springer Nature Link
SN 2180-4206
YR 2025
FD 2025
LK http://hdl.handle.net/10498/36489
UL http://hdl.handle.net/10498/36489
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 10-may-2026