Reconfiguration graphs of mutual-visibility sets
Abstract
A set S⊆ V(G) is a mutual-visibility set if every pair of vertices in S is joined by a geodesic whose internal vertices do not belong to S. We define a reconfiguration graph whose vertices are the mutual-visibility sets of G. Two configurations are adjacent if one is obtained from the other by adding or removing one vertex or by sliding one token along an edge of G. The subgraphs induced by configurations of a fixed cardinality are called layers. The spanning subgraph formed by token-addition and token-removal edges is a daisy cube. We study the effects of token-sliding edges on distances and connectivity to this skeleton. For a connected host of order n≥3, the vertex connectivity of the reconfiguration graph lies between $3$ and n, and both bounds are attained. We determine several parameters of ℛℳ(Kn) and describe the behavior of the model for disconnected hosts and for isometric or convex subgraphs. We also give a component-based criterion for mobile mutual visibility. For complete bipartite graphs, we use a description of feasible configurations to determine connectivity and distance bounds for fixed-cardinality layers. For trees, we show that every component of a layer of cardinality at least three is isomorphic to a Cartesian product of subtrees, obtaining exact metric formulas and characterizing the connected layers. Finally, we prove that every layer of a cycle is connected.
Related
- Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number
- Connected Mutual-Visibility in Graphs
- A variety of the mutual-visibility coloring problem for graphs
- Mutual-visibility colouring with two colours is NP-complete for every fixed diameter
- Simultaneous visibility in cut-and-project sets
BibTeX
@misc{fresanfigueroa2026reconfiguration,
title = {{Reconfiguration graphs of mutual-visibility sets}},
author = {Julián A. Fresán-Figueroa and Ilán A. Goldfeder and Aldo Lozano-Piña},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24324},
eprint = {2610.24324},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24324},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Reconfiguration graphs of mutual-visibility sets
AU - Julián A. Fresán-Figueroa
AU - Ilán A. Goldfeder
AU - Aldo Lozano-Piña
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.24324
UR - https://arxiv.org/abs/2610.24324
AB - A set S⊆ V(G) is a mutual-visibility set if every pair of vertices in S is joined by a geodesic whose internal vertices do not belong to S. We define a reconfiguration graph whose vertices are the mutual-visibility sets of G. Two configurations are adjacent if one is obtained from the other by adding or removing one vertex or by sliding one token along an edge of G. The subgraphs induced by configurations of a fixed cardinality are called layers. The spanning subgraph formed by token-addition and token-removal edges is a daisy cube. We study the effects of token-sliding edges on distances and connectivity to this skeleton. For a connected host of order n≥3, the vertex connectivity of the reconfiguration graph lies between $3$ and n, and both bounds are attained. We determine several parameters of ℛ_ℳ(K_n) and describe the behavior of the model for disconnected hosts and for isometric or convex subgraphs. We also give a component-based criterion for mobile mutual visibility. For complete bipartite graphs, we use a description of feasible configurations to determine connectivity and distance bounds for fixed-cardinality layers. For trees, we show that every component of a layer of cardinality at least three is isomorphic to a Cartesian product of subtrees, obtaining exact metric formulas and characterizing the connected layers. Finally, we prove that every layer of a cycle is connected.
ER -