| Title: | Mobile mutual-visibility sets in graphs |
|---|
| Authors: | ID Dettlaff, Magda (Author)
ID Lemańska, Magdalena (Author)
ID Rodríguez-Velázquez, Juan A. (Author)
ID Yero, Ismael G. (Author) |
|---|
| Files: |  AMC_Dettlaff,_Lemańska,_Rodriguez-Velazquez,_G._Yero_2026.pdf (398,89 KB)
MD5: A24E12A12BD5890262614431BFA2F7D3
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | ZUP - University of Primorska Press
|
|---|
| 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. |
|---|
| Keywords: | mobile mutual-visibility set, mutual-visibility number, total mutual-visibility |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 18.12.2025 |
|---|
| Publisher: | Založba Univerze na Primorskem |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | 21 str. |
|---|
| Numbering: | Vol. 26, no. 1, [article no.] P1.10 |
|---|
| PID: | 20.500.12556/RUP-22688  |
|---|
| UDC: | 51 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | 10.26493/1855-3974.3410.9bc |
|---|
| Publication date in RUP: | 03.03.2026 |
|---|
| Views: | 167 |
|---|
| Downloads: | 12 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
