Mobile mutual-visibility sets in graphs

Magdalena Lemańska; Magda Dettlaff; Juan Alberto Rodriguez-Velazquez; Ismael Gonzalez Yero

doi:10.26493/1855-3974.3410.9bc

Mobile mutual-visibility sets in graphs

Abstract

Given a connected graph G, the mutual-visibility number of G is the cardinality of a largest set S such that for every pair of vertices x, y ∈ S there exists a shortest x, y-path whose interior vertices are not contained in S. Assume that a robot is assigned to each vertex of the set S. At each stage, one robot can move to a neighbouring vertex. Then S is a mobile mutual-visibility set of G if there exists a sequence of moves of the robots such that all the vertices of G are visited while maintaining the mutual-visibility property at all times. The mobile mutual-visibility number of G, denoted Mobμ(G), is the cardinality of a largest mobile mutual-visibility set of G. In this paper we introduce the concept of the mobile mutual-visibility number of a graph. We begin with some basic properties of the mobile mutual-visibility number of G and its relationship with the mutual-visibility number 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 characterizations of the graphs achieving the limit values of some of these bounds. As a consequence of this study, we deduce that the decision problem concerning finding the mobile mutual-visibility number is NP-hard. Finally, we focus our attention on the mobile mutual-visibility number of line graphs of complete graphs, prism graphs and strong grids of two paths.

Citations

0

CrossRef
0

Web of Science
0

Scopus

Authors (4)

Magdalena Lemańska dr inż.
- Faculty of Applied Physics and Mathematics
- Gdańsk University of Technology
Magda Dettlaff dr
Juan Alberto Rodriguez-Velazquez Prof
Ismael Gonzalez Yero

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

MOBILE MUTUAL-VISIBILITY SET, MUTUAL-VISIBILITY NUMBER, TOTAL MUTUAL-VISIBILITY.

Details

Category:

Articles

Type:

artykuły w czasopismach dostępnych w wersji elektronicznej [także online]

Published in:

ARS Mathematica Contemporanea
ISSN: 1855-3966

Language:

English

Publication year:

2025

Bibliographic description:

Lemańska M., Dettlaff M., Rodriguez-Velazquez J. A., Yero I. G., Mobile mutual-visibility sets in graphs, ARS Mathematica Contemporanea, 2025,10.26493/1855-3974.3410.9bc

DOI: