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

Abstrakt

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.

Cytowania

0

CrossRef
0

Web of Science
0

Scopus

Autorzy (4)

Magdalena Lemańska dr inż.
- Wydział Fizyki Technicznej i Matematyki Stosowanej
- Politechnika Gdańska
Magda Dettlaff dr
Juan Alberto Rodriguez-Velazquez Prof
Ismael Gonzalez Yero

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

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

Informacje szczegółowe

Kategoria:

Publikacja w czasopiśmie

Typ:

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

Opublikowano w:

ARS Mathematica Contemporanea
ISSN: 1855-3966

Język:

angielski

Rok wydania:

2025

Opis bibliograficzny:

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: