betaFeedback

WorksMathematics

Reconfiguration graphs of mutual-visibility sets

Abstract

A set S⊆V(G)S\subseteq V(G) is a mutual-visibility set if every pair of vertices in SS is joined by a geodesic whose internal vertices do not belong to SS. We define a reconfiguration graph whose vertices are the mutual-visibility sets of GG. 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 GG. 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≥3n\ge3, the vertex connectivity of the reconfiguration graph lies between 33 and nn, and both bounds are attained. We determine several parameters of RM(Kn)\mathcal{R}_{\mathcal{M}}(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.

Introduction

Mutual visibility in graphs was introduced by Di Stefano [5]. A set S⊆V(G)S \subseteq V(G) is a mutual-visibility set if, for every pair of distinct vertices u,v∈Su, v \in S, there exists a uvuv-geodesic whose internal vertices do not belong to SS. We denote the family of these sets by M(G)\mathcal{M}(G) and put Mk(G)={S∈M(G):∣S∣=k}\mathcal{M}_k(G) = \{S \in\mathcal{M}(G) : |S| = k\}. The maximum cardinality of a set in M(G)\mathcal{M}(G) is the mutual-visibility number μ(G)\mu(G). Variants and structural aspects have been studied by Cicerone et al. [3], Korže and Vesel [10], Bujtás et al. [2] and Tonny K B and Shikhi M [14], among others.

Extremal parameters give the largest feasible cardinality; reconfiguration studies how feasible solutions can be transformed into one another through allowed local operations. For an introduction to reconfiguration problems, see Nishimura [12].

ISSN subm. to DMTCS © by the authors by the author(s) Distributed under a Creative Commons Attribution 4.0 International License Here, configurations are the mutual-visibility sets of a graph GG. We allow token addition/removal (TAR) and token sliding (TS). A TS move transfers a token to an unoccupied adjacent vertex. The resulting graph is denoted by RM(G)\mathcal{R}_{M}(G); we call GG the host graph. The configurations of cardinality kk induce the kk-th layer, denoted by RMk(G)\mathcal{R}_{M}^{k}(G). Only token slides occur within layers, so RMk(G)\mathcal{R}_{M}^{k}(G) is an induced subgraph of the kk-token graph of GG [7]. A mixed reconfiguration model involving the same operations was considered for domination in Messinger and Pipes [11].

Token sliding also appears in mobile mutual visibility [4, 13]. The two models ask different questions. Mobility requires a sequence starting from one configuration in which the tokens collectively visit every vertex of the host graph, whereas reconfiguration concerns reachability between two prescribed configurations. We characterize mobility through a covering condition on a connected component of a layer.

We first study the full graph RM(G)\mathcal{R}_{M}(G). Heredity identifies its TAR skeleton as a daisy cube. We examine how TS edges affect distances and connectivity and study disconnected hosts as well as isometric and convex subgraphs, and determine the parameters for complete graphs.

We then study fixed-cardinality layers. For complete bipartite graphs, we use feasible types to determine connectivity of fixed-cardinality layers and to bound distances within connected layers. Earlier results on maximal sets and visibility polynomials provide context for the accompanying enumeration [1, 2]. For trees, active branching vertices act as barriers, leading to a Cartesian-product decomposition of each component, giving exact order, size, and diameter formulas. Every layer of a cycle is connected. Our main contributions are structural results about reconfiguration, together with some enumeration formulas; known extremal and mobile values are cited as inputs or recovered structurally.

Preliminaries and the reconfiguration model

All graphs are finite, simple, undirected, and connected, unless stated otherwise. We follow Diestel [6] for standard graph terminology and notation. For a connected graph HH, we write dHd_H for its distance function and diam⁡(H)\operatorname{diam}(H) for its diameter.

Equivalently, a set S⊆V(G)S \subseteq V(G) belongs to M(G)\mathcal{M}(G) if every pair of distinct vertices u,v∈Su,v \in S is joined by a uvuv-geodesic PP such that V(P)∩S={u,v}V(P) \cap S = \{u,v\}. We will repeatedly use the following heredity property.

Proposition 2.1 [3]. If SS is a mutual-visibility set of a graph GG and S′⊆SS' \subseteq S, then S′S' is also a mutual-visibility set of GG.

Consequently, Mk(G)≠∅\mathcal{M}_{k}(G) \ne\varnothing for every 0≤k≤μ(G)0 \le k \le\mu(G). The mutual-visibility reconfiguration graph RM(G)\mathcal{R}_{M}(G) has vertex set M(G)\mathcal{M}(G), and two distinct configurations S,T∈M(G)S,T \in\mathcal{M}(G) are adjacent if either ∣S△T∣=1|S \mathbin{\triangle} T|=1, or there exist vertices x,y∈V(G)x,y \in V(G) such that S∖T={x}S \setminus T = \{x\} and T∖S={y}T \setminus S = \{y\}, with xy∈E(G)xy \in E(G). Moves of the first type are token addition/removal (TAR) move; moves of the second type are token-sliding (TS) moves from xx to its unoccupied neighbor yy (Figure 1). For 0≤k≤μ(G)0 \le k \le\mu(G), the subgraph of RM(G)\mathcal{R}_{M}(G) induced by Mk(G)\mathcal{M}_{k}(G) is denoted by RMk(G)\mathcal{R}_{M}^{k}(G) and is called the kk-th layer. Thus TAR move joins distinct layers, and TS moves stay within a layer. We call a move admissible if the resulting configuration belongs to M(G)\mathcal{M}(G).

Two move types in the reconfiguration model

Figure 1. The two move types in RM(G)\mathcal{R}_{\mathcal{M}}(G). Red vertices carry tokens. Every displayed configuration belongs to M(G)\mathcal{M}(G). A fixed-cardinality layer contains only TS moves.

For 0≤k≤∣V(G)∣0 \le k \le|V(G)|, the vertices of the kk-token graph Tk(G)\mathcal{T}_{k}(G) are the kk-subsets of V(G)V(G); two such sets SS and TT are adjacent if and only if S△T={x,y}S \mathbin{\triangle} T = \{x,y\}, with {x,y}∈E(G)\{x,y\} \in E(G). Token graphs were introduced by Fabila-Monroy et al. [7], who proved the following result.

Theorem 2.2 (Fabila-Monroy et al., [7]). Let GG be a connected graph, and let 1≤k<∣V(G)∣1 \le k < |V(G)|. Then Tk(G)\mathcal{T}_k(G) is connected with diameter at least k(diam⁡(G)−k+1)k(\operatorname{diam}(G)-k+1) and at most kdiam⁡(G)k\operatorname{diam}(G).

The cases k=0k=0 and k=∣V(G)∣k=|V(G)| each give a single vertex. By definition, RMk(G)\mathcal{R}^{k}_{\mathcal{M}}(G) is the subgraph of Tk(G)\mathcal{T}_k(G) induced by Mk(G)\mathcal{M}_k(G).

The model also admits a hypercube representation. The nn-dimensional hypercube QnQ_n has vertex set {0,1}n\{0,1\}^n, with two vectors adjacent if they differ in exactly one coordinate. Let n=∣V(G)∣n=|V(G)| and identify each subset of V(G)V(G) with its incidence vector in {0,1}n\{0,1\}^n. Under this identification, the TAR edges of RM(G)\mathcal{R}_{\mathcal{M}}(G) form the subgraph of QnQ_n induced by the incidence vectors of the sets in M(G)\mathcal{M}(G). The full graph RM(G)\mathcal{R}_{\mathcal{M}}(G) is obtained from this induced subgraph by adding the TS edges within each layer.

We next introduce mobile mutual visibility. In the mobile mutual-visibility model, an admissible TS move is called a legal mobile move. A set S∈Mk(G)S \in\mathcal{M}_k(G) is a mobile mutual-visibility set if there exists a finite sequence S0,S1,…,SrS_0,S_1,\ldots,S_r of configurations in Mk(G)\mathcal{M}_k(G), with S0=SS_0=S, such that consecutive configurations differ by a legal mobile move and ⋃i=0rSi=V(G)\bigcup_{i=0}^{r}S_i=V(G). The mobile mutual-visibility number of GG, denoted by Mob⁡μ(G)\operatorname{Mob}_{\mu}(G), is the largest integer kk such that Mk(G)\mathcal{M}_k(G) contains a mobile mutual-visibility set. Dettlaff et al. [4] introduced this model. The next criterion follows from the reversibility of legal moves for mobile position problems; compare Dettlaff et al. [4] and Shallcross et al. [13].

Proposition 2.3 (Component criterion for mobility). Let GG be a graph, let 0≤k≤μ(G)0 \le k \le\mu(G), and let S∈Mk(G)S \in\mathcal{M}_k(G). Let Ck(S)C_k(S) denote the connected component of RMk(G)\mathcal{R}^{k}_{\mathcal{M}}(G) containing SS. Then SS is a mobile mutual-visibility set if and only if ⋃X∈V(Ck(S))X=V(G)\bigcup_{X\in V(C_k(S))}X=V(G).

Proof: A walk in Ck(S)C_k(S) corresponds to a sequence of configurations in Mk(G)\mathcal{M}_k(G) in which consecutive configurations differ by a legal mobile move.

Suppose that SS is a mobile mutual-visibility set. Let S0,S1,…,SrS_0,S_1,\ldots,S_r be a witnessing sequence, so S0=SS_0=S and ⋃i=0rSi=V(G)\bigcup_{i=0}^{r}S_i=V(G). It determines a walk starting at SS. Hence every SiS_i belongs to Ck(S)C_k(S), and

V(G)=⋃i=0rSi⊆⋃X∈V(Ck(S))X⊆V(G).V(G)=\bigcup_{i=0}^{r}S_i\subseteq\bigcup_{X\in V(C_k(S))}X\subseteq V(G).

This proves the required covering condition.

Conversely, assume the covering condition. Since the component is finite and connected, there is a walk (S0,S1,…,Sr)(S_0,S_1,\ldots,S_r) starting at SS and visiting every vertex of Ck(S)C_k(S). Each step of this walk corresponds to a legal mobile move, and

⋃i=0rSi=⋃X∈V(Ck(S))X=V(G).\bigcup_{i=0}^{r}S_i=\bigcup_{X\in V(C_k(S))}X=V(G).

Thus, SS is a mobile mutual-visibility set.

Corollary 2.4. Let GG be a graph and let 0≤k≤μ(G)0 \le k \le\mu(G). If RMk(G)\mathcal{R}^{k}_{M}(G) is connected, then every member of Mk(G)\mathcal{M}_{k}(G) is mobile if and only if every vertex of GG belongs to at least one member of Mk(G)\mathcal{M}_{k}(G).

Proposition 2.3 connects mobility, which asks whether a component covers the host, with reachability between configurations.

In a connected graph GG, every vertex subset of cardinality at most two is a mutual-visibility set. It follows that ∣Mk(G)∣=(∣V(G)∣k)|\mathcal{M}_{k}(G)| = \binom{|V(G)|}{k} for k∈{0,1,2}k \in\{0,1,2\}. Therefore, RM0(G)≅K1\mathcal{R}^{0}_{M}(G) \cong K_{1}, RM1(G)≅G\mathcal{R}^{1}_{M}(G) \cong G, and RM2(G)=T2(G)\mathcal{R}^{2}_{M}(G) = T_{2}(G). In particular, these layers are connected. If GG has at least two vertices, the configurations in RM2(G)\mathcal{R}^{2}_{M}(G) also cover V(G)V(G), and Corollary 2.4 gives 2≤Mob⁡μ(G)≤μ(G)2 \le\operatorname{Mob}_{\mu}(G) \le\mu(G). Thus only layers of cardinality at least three can be disconnected. We first study the full reconfiguration graph, then layers for specific families.

Structural properties of the full reconfiguration graph

The full graph combines TAR moves between layers with TS moves within them. We show that its TAR skeleton is a daisy cube and derive results on distances, enumeration, and vertex connectivity, and examine complete and disconnected hosts and isometric and convex subgraphs.

The TAR skeleton and metric bounds

Let GG be a graph of order nn. The TAR skeleton of RM(G)\mathcal{R}_{M}(G), denoted by RTAR(G)\mathcal{R}_{\mathrm{TAR}}(G), is the spanning subgraph obtained by deleting all TS edges. Fix an ordering v1,…,vnv_{1},\ldots,v_{n} of V(G)V(G) and identify each subset S⊆V(G)S \subseteq V(G) with its incidence vector χS∈{0,1}n\chi_{S} \in\{0,1\}^{n}, where (χS)i=1(\chi_{S})_{i}=1 if vi∈Sv_{i} \in S and (χS)i=0(\chi_{S})_{i}=0 otherwise. Thus subsets of V(G)V(G) are identified with vertices of QnQ_{n}.

For X⊆{0,1}nX \subseteq\{0,1\}^{n}, let Qn(X)Q_{n}(X) denote the subgraph of QnQ_{n} induced by the vectors y=(y1,…,yn)∈{0,1}ny=(y_{1},\ldots,y_{n}) \in\{0,1\}^{n} for which there exists x=(x1,…,xn)∈Xx=(x_{1},\ldots,x_{n}) \in X satisfying yi≤xiy_{i} \le x_{i} for every i∈{1,…,n}i \in\{1,\ldots,n\}. A graph of this form is called a daisy cube. A subgraph HH of GG is isometric if dH(u,v)=dG(u,v)d_{H}(u,v)=d_{G}(u,v) for all u,v∈V(H)u,v \in V(H). A partial cube is a graph isomorphic to an isometric subgraph of a hypercube.

Proposition 3.1 [9]. If X⊆{0,1}nX \subseteq\{0,1\}^{n}, then Qn(X)Q_{n}(X) is a partial cube.

Theorem 3.2 (The TAR skeleton). Let GG be a graph of order nn, and let M^(G)\widehat{\mathcal{M}}(G) be the family of inclusion-maximal mutual-visibility sets of GG. Under the incidence-vector identification, RTAR(G)=Qn(M^(G))\mathcal{R}_{\mathrm{TAR}}(G)=Q_{n}(\widehat{\mathcal{M}}(G)). In particular, RTAR(G)\mathcal{R}_{\mathrm{TAR}}(G) is a daisy cube. Moreover, for all S,T∈M(G)S,T \in\mathcal{M}(G), we have dRTAR(G)(S,T)=∣S△T∣d_{\mathcal{R}_{\mathrm{TAR}}(G)}(S,T)=|S\mathbin{\triangle}T|. Consequently, RTAR(G)\mathcal{R}_{\mathrm{TAR}}(G) is an isometric subgraph of QnQ_{n} and, in particular, a partial cube.

Proof. Heredity makes M(G)\mathcal{M}(G) downward closed, and each of its members lies in an inclusion-maximal member. Thus its incidence vectors form the downset generated by M^(G)\widehat{\mathcal{M}}(G); TAR adjacency agrees with hypercube adjacency. This proves the daisy-cube description, and Proposition 3.1 gives the partial-cube assertion.

For S,T∈M(G)S,T \in\mathcal{M}(G), remove the vertices of S∖TS \setminus T one at a time and then add those of T∖ST \setminus S. Every intermediate set is a subset of SS or TT, so the resulting TAR path has length ∣S△T∣|S\mathbin{\triangle}T|. Any hypercube path must change at least these ∣S△T∣|S\mathbin{\triangle}T| coordinates. This proves the distance formula and isometry.

The TS edges may shorten distances relative to the TAR skeleton. The next bounds are expressed in terms of ∣S∖T∣|S \setminus T| and ∣T∖S∣|T \setminus S|.

Proposition 3.3 (Metric bounds). Let GG be a graph of order nn. For all S,T∈M(G)S,T \in\mathcal{M}(G), the inequality max⁡{∣S∖T∣,∣T∖S∣}≤dRM(G)(S,T)≤∣S△T∣\max\{|S \setminus T|, |T \setminus S|\} \le d_{\mathcal{R}_{\mathcal{M}}(G)}(S,T) \le|S \mathbin{\triangle} T| holds. If S⊆TS \subseteq T, then dRM(G)(S,T)=∣T∖S∣d_{\mathcal{R}_{\mathcal{M}}(G)}(S,T) = |T \setminus S|. In particular, dRM(G)(∅,S)=∣S∣d_{\mathcal{R}_{\mathcal{M}}(G)}(\varnothing,S) = |S| and ecc⁡RM(G)(∅)=μ(G)\operatorname{ecc}_{\mathcal{R}_{\mathcal{M}}(G)}(\varnothing) = \mu(G), where ecc⁡\operatorname{ecc} denotes eccentricity. Consequently, μ(G)≤diam⁡(RM(G))≤min⁡{n,2μ(G)}\mu(G) \le\operatorname{diam}(\mathcal{R}_{\mathcal{M}}(G)) \le\min\{n,2\mu(G)\}.

Proof. Each move removes at most one vertex of S∖TS \setminus T and inserts at most one vertex of T∖ST \setminus S. Hence every STST-path has length at least max⁡{∣S∖T∣,∣T∖S∣}\max\{|S \setminus T|, |T \setminus S|\}. The preceding theorem gives a TAR path of length ∣S△T∣|S \mathbin{\triangle} T|, proving the upper bound. If S⊆TS \subseteq T, both bounds equal ∣T∖S∣|T \setminus S|. Taking S=∅S = \varnothing gives ecc⁡RM(G)(∅)=μ(G)\operatorname{ecc}_{\mathcal{R}_{\mathcal{M}}(G)}(\varnothing) = \mu(G) and thus diam⁡(RM(G))≥μ(G)\operatorname{diam}(\mathcal{R}_{\mathcal{M}}(G)) \ge\mu(G). Finally, ∣S△T∣≤min⁡{n,∣S∣+∣T∣}≤min⁡{n,2μ(G)}|S \mathbin{\triangle} T| \le\min\{n,|S|+|T|\} \le\min\{n,2\mu(G)\}.

Every TS edge can be replaced by a two-edge path in the TAR skeleton. Indeed, if SS and TT are TS-adjacent, then S∩T∈M(G)S \cap T \in\mathcal{M}(G), and both SS and TT are TAR-adjacent to S∩TS \cap T. Hence these three configurations form a 3-cycle in RM(G)\mathcal{R}_{\mathcal{M}}(G).

Counting configurations, TAR edges, and local structure

The visibility polynomial of GG was introduced by Bujtás et al. [2]. In our notation, it is given by PG(z)=∑k=0μ(G)mkzkP_G(z) = \sum_{k=0}^{\mu(G)} m_k z^k, where mk=∣Mk(G)∣m_k = |\mathcal{M}_k(G)|.

For a daisy cube H=Qd(X)H = Q_d(X), its cube polynomial is CH(z)=∑j≥0cj(H)zjC_H(z) = \sum_{j \ge0} c_j(H)z^j, where cj(H)c_j(H) is the number of induced subgraphs of HH isomorphic to QjQ_j. Writing 0d0^d for the all-zero vector, its weight enumerator with respect to 0d0^d is WH,0d(z)=∑v∈V(H)zdH(0d,v)W_{H,0^d}(z) = \sum_{v \in V(H)} z^{d_H(0^d,v)}. We recall the cube-polynomial identity from the following result.

Corollary 3.4 [9]. If H=Qd(X)H = Q_d(X) is a daisy cube, then CH(z)=WH,0d(z+1)C_H(z) = W_{H,0^d}(z+1).

By Theorem 3.2, WRTAR(G),∅(z)=PG(z)W_{\mathcal{R}_{\mathrm{TAR}}(G),\varnothing}(z) = P_G(z), so Corollary 3.4 gives CRTAR(G)(z)=PG(z+1)C_{\mathcal{R}_{\mathrm{TAR}}(G)}(z) = P_G(z+1). Since c0(H)=∣V(H)∣c_0(H) = |V(H)| and c1(H)=∣E(H)∣c_1(H) = |E(H)|, the constant and linear coefficients give the two identities below. We also give a direct counting proof.

Proposition 3.5. The order and number of TAR edges are ∣V(RM(G))∣=∑k=0μ(G)mk=PG(1)|V(\mathcal{R}_{\mathcal{M}}(G))| = \sum_{k=0}^{\mu(G)} m_k = P_G(1) and ∣E(RTAR(G))∣=∑k=1μ(G)kmk=PG′(1)|E(\mathcal{R}_{\mathrm{TAR}}(G))| = \sum_{k=1}^{\mu(G)} km_k = P'_G(1).

Proof. Every configuration in M(G)\mathcal{M}(G) belongs to exactly one of the families Mk(G)\mathcal{M}_k(G), according to its cardinality. Therefore, ∣V(RM(G))∣=∑k=0μ(G)∣Mk(G)∣=PG(1)|V(\mathcal{R}_{\mathcal{M}}(G))| = \sum_{k=0}^{\mu(G)} |\mathcal{M}_k(G)| = P_G(1). Each configuration in Mk(G)\mathcal{M}_k(G) has kk TAR neighbors in Mk−1(G)\mathcal{M}_{k-1}(G), one per token removal. Counting from the larger endpoint counts each TAR edge once. Hence, ∣E(RTAR(G))∣=∑k=1μ(G)k∣Mk(G)∣=PG′(1)|E(\mathcal{R}_{\mathrm{TAR}}(G))| = \sum_{k=1}^{\mu(G)} k|\mathcal{M}_k(G)| = P'_G(1).

For a set S∈M(G)S \in\mathcal{M}(G), the neighbors of SS fall into three disjoint classes: token removals, token additions, and token slides. Heredity makes each of the ∣S∣|S| possible removals admissible. To count the remaining two types of neighbors, define sG(S)=∣{(x,y)∈S×(V(G)∖S):xy∈E(G),(S∖{x})∪{y}∈M(G)}∣s_G(S) = |\{(x,y) \in S \times(V(G) \setminus S): xy \in E(G), (S \setminus\{x\}) \cup\{y\} \in\mathcal{M}(G)\}| and aG(S)=∣{v∈V(G)∖S:S∪{v}∈M(G)}∣a_G(S) = |\{v \in V(G) \setminus S: S \cup\{v\} \in\mathcal{M}(G)\}|. These count admissible slides and additions, respectively. Therefore, deg⁡RM(G)(S)=∣S∣+aG(S)+sG(S)\deg_{\mathcal{R}_{\mathcal{M}}(G)}(S) = |S| + a_G(S) + s_G(S). In particular, deg⁡RM(G)(∅)=n\deg_{\mathcal{R}_{\mathcal{M}}(G)}(\varnothing) = n.

Vertex connectivity

Theorem 3.6 (Vertex connectivity). Let GG be a connected graph of order n≥3n \ge3. Then the reconfiguration graph satisfies 3≤κ(RM(G))≤n3 \le\kappa(\mathcal{R}_{\mathcal{M}}(G)) \le n. Both bounds are sharp. Proof: The empty configuration has precisely nn neighbors, namely the singleton configurations. Deleting these neighbors isolates ∅\emptyset, and therefore κ(RM(G))≤n\kappa(\mathcal{R}_{\mathcal{M}}(G)) \le n.

To prove the lower bound, let F⊆V(RM(G))F \subseteq V(\mathcal{R}_{\mathcal{M}}(G)) with ∣F∣≤2|F| \le2. We show that RM(G)−F\mathcal{R}_{\mathcal{M}}(G)-F is connected. Let HH be the subgraph of RM(G)−F\mathcal{R}_{\mathcal{M}}(G)-F induced by the remaining configurations of cardinality at most two. We first prove that HH is connected and then show that every remaining larger configuration has a path to HH.

Suppose first that ∅∉F\emptyset\notin F. Every remaining singleton configuration is adjacent to ∅\emptyset. A remaining configuration {u,v}\{u,v\} of cardinality two is adjacent to one of these singletons unless both {u}\{u\} and {v}\{v\} belong to FF. If both belong to FF, then F={{u},{v}}F=\{\{u\},\{v\}\}. Since GG is connected and n≥3n \ge3, there exist x∈{u,v}x \in\{u,v\} and w∉{u,v}w \notin\{u,v\} such that xw∈E(G)xw \in E(G). Sliding the token from xx to ww yields the configuration U=({u,v}∖{x})∪{w}U=(\{u,v\}\setminus\{x\})\cup\{w\}. Neither UU nor {w}\{w\} belongs to FF. Thus, {u,v}\{u,v\} is joined to ∅\emptyset by the path {u,v},U,{w},∅\{u,v\}, U, \{w\}, \emptyset, which lies entirely in HH. Thus every vertex reaches ∅\emptyset, so HH is connected.

Suppose now that ∅∈F\emptyset\in F. Before deleting the configurations in FF, the TAR edges between M1(G)\mathcal{M}_1(G) and M2(G)\mathcal{M}_2(G) form the graph obtained by subdividing every edge of KnK_n once. Singletons correspond to original vertices, and {u,v}\{u,v\} subdivides the edge joining {u}\{u\} and {v}\{v\}.

Since ∅∈F\emptyset\in F and ∣F∣≤2|F| \le2, at most one vertex of this subdivision graph is deleted. If none is deleted, the graph remains connected. Deleting a configuration of cardinality two leaves a subdivision of KnK_n with one edge removed, which is connected because n≥3n \ge3. Deleting a singleton configuration leaves a subdivision of Kn−1K_{n-1} together with pendant vertices, each attached to a remaining singleton configuration. This graph is also connected. In each case, the remaining TAR edges connect HH.

Now let S∈V(RM(G))∖FS \in V(\mathcal{R}_{\mathcal{M}}(G)) \setminus F with ∣S∣≥3|S| \ge3. Every configuration XX of cardinality at least three has at least three distinct TAR neighbors of cardinality ∣X∣−1|X|-1, namely the configurations X∖{x}X\setminus\{x\} with x∈Xx \in X. Heredity makes these configurations feasible. Since ∣F∣≤2|F| \le2, at least one of these neighbors lies outside FF. Repeating this deletion step produces a TAR path from SS to HH in RM(G)−F\mathcal{R}_{\mathcal{M}}(G)-F.

Finally, let AA and BB be any two vertices of RM(G)−F\mathcal{R}_{\mathcal{M}}(G)-F. Each has a path to HH, possibly of length zero. Connecting these paths through HH gives an ABAB-walk in RM(G)−F\mathcal{R}_{\mathcal{M}}(G)-F. Thus, RM(G)−F\mathcal{R}_{\mathcal{M}}(G)-F is connected. Since FF was arbitrary, κ(RM(G))≥3\kappa(\mathcal{R}_{\mathcal{M}}(G)) \ge3.

Both bounds are attained. For the lower bound, let G=PnG=P_n with n≥3n \ge3, and let v1v_1 be an end vertex with neighbor v2v_2. A mutual-visibility set of a path has at most two vertices. The configuration {v1,v2}\{v_1,v_2\} has two TAR neighbors and exactly one TS neighbor, obtained by sliding the token on v2v_2 to v3v_3. Hence, its degree is three, and the lower bound gives κ(RM(Pn))=3\kappa(\mathcal{R}_{\mathcal{M}}(P_n))=3.

For the upper bound, let G=KnG=K_n. Every subset of V(Kn)V(K_n) is a mutual-visibility set, so the TAR skeleton of RM(Kn)\mathcal{R}_{\mathcal{M}}(K_n) is QnQ_n. The spanning nn-connected subgraph QnQ_n gives κ(RM(Kn))≥n\kappa(\mathcal{R}_{\mathcal{M}}(K_n)) \ge n. Therefore κ(RM(Kn))=n\kappa(\mathcal{R}_{\mathcal{M}}(K_n))=n.

A natural question is whether RM(G)\mathcal{R}_{\mathcal{M}}(G) is maximally connected for every connected GG, that is, whether κ(RM(G))=δ(RM(G))\kappa(\mathcal{R}_{\mathcal{M}}(G))=\delta(\mathcal{R}_{\mathcal{M}}(G)) holds, where δ\delta denotes minimum degree? The theorem settles this for its two extremal families.

The complete graph

For complete graphs, every configuration is feasible and the parameters in Proposition 3.7 admit closed formulas. For integers nn and kk with 0≤k≤n0 \le k \le n, the vertices of the Johnson graph J(n,k)\mathcal{J}(n,k) are the kk-subsets of an nn-element set. Adjacency in J(n,k)\mathcal{J}(n,k) means ∣S△T∣=2|S\triangle T|=2, a single-element replacement.

Proposition 3.7. Let n≥3n \ge3 and 0≤k≤n0 \le k \le n. The layer RMk(Kn)\mathcal{R}_{\mathcal{M}}^k(K_n) is isomorphic to J(n,k)\mathcal{J}(n,k), and RM(Kn)\mathcal{R}_{\mathcal{M}}(K_n) is obtained from QnQ_n by adding the edges of J(n,k)\mathcal{J}(n,k) within each level kk. Moreover, for configurations

S,T⊆V(Kn),S,T \subseteq V(K_n),

  1. ∣V(RM(Kn))∣=∣M(Kn)∣=2n|V(\mathcal{R}_{\mathcal{M}}(K_n))|=|\mathcal{M}(K_n)|=2^n.

  2. ∣E(RM(Kn))∣=n(n+3)2n−3|E(\mathcal{R}_{\mathcal{M}}(K_n))|=n(n+3)2^{n-3}.

  3. If ∣S∣=k|S|=k, then deg⁡RM(Kn)(S)=n+k(n−k)\deg_{\mathcal{R}_{\mathcal{M}}(K_n)}(S)=n+k(n-k).

  4. dRM(Kn)(S,T)=max⁡{∣S∖T∣,∣T∖S∣}d_{\mathcal{R}_{\mathcal{M}}(K_n)}(S,T)=\max\{|S\setminus T|,|T\setminus S|\}.

  5. diam⁡(RM(Kn))=n\operatorname{diam}(\mathcal{R}_{\mathcal{M}}(K_n))=n.

  6. The radius is rad⁡(RM(Kn))=⌈n/2⌉\operatorname{rad}(\mathcal{R}_{\mathcal{M}}(K_n))=\lceil n/2\rceil.

  7. The center of RM(Kn)\mathcal{R}_{\mathcal{M}}(K_n) consists of the configurations of cardinality ⌊n/2⌋\lfloor n/2\rfloor and ⌈n/2⌉\lceil n/2\rceil.

  8. κ(RM(Kn))=n\kappa(\mathcal{R}_{\mathcal{M}}(K_n))=n.

Proof: Every subset of V(Kn)V(K_n) is a mutual-visibility set. Consequently, the TAR edges form QnQ_n, whereas the TS edges in level kk form J(n,k)\mathcal{J}(n,k). This proves the structural description and (1).

To prove (2) and (3), let SS be a configuration of cardinality kk. Each TS neighbor of SS is uniquely obtained by choosing a vertex x∈Sx\in S and a vertex y∈V(Kn)∖Sy\in V(K_n)\setminus S, and replacing xx with yy. Hence, SS has exactly k(n−k)k(n-k) TS neighbors. It also has kk deletion neighbors and n−kn-k addition neighbors. Therefore, deg⁡RM(Kn)(S)=k+(n−k)+k(n−k)=n+k(n−k)\deg_{\mathcal{R}_{\mathcal{M}}(K_n)}(S)=k+(n-k)+k(n-k)=n+k(n-k), proving (3).

The TAR skeleton has n2n−1n2^{n-1} edges. The sum ∑k=0n(nk)k(n−k)=n(n−1)2n−2\sum_{k=0}^{n}\binom{n}{k}k(n-k)=n(n-1)2^{n-2} counts triples (S,x,y)(S,x,y) with x∈Sx\in S and y∉Sy\notin S: choose the ordered pair (x,y)(x,y) in n(n−1)n(n-1) ways and the remaining memberships in 2n−22^{n-2} ways. Each TS edge is counted twice. Therefore ∣E(RM(Kn))∣=n2n−1+n(n−1)2n−3=n(n+3)2n−3|E(\mathcal{R}_{\mathcal{M}}(K_n))|=n2^{n-1}+n(n-1)2^{n-3}=n(n+3)2^{n-3}, proving (2).

For the distance formula, let A=S∖TA=S\setminus T and B=T∖SB=T\setminus S, and put a=∣A∣a=|A| and b=∣B∣b=|B|. Consider an arbitrary STST-path of length ℓ\ell. Every vertex of AA must be removed. Since each move removes at most one vertex of AA, we have ℓ≥a\ell\ge a. Every vertex of BB must be inserted; at most one is inserted per move, so ℓ≥b\ell\ge b. Therefore, ℓ≥max⁡{a,b}\ell\ge\max\{a,b\}. Thus dRM(Kn)(S,T)≥max⁡{a,b}d_{\mathcal{R}_{\mathcal{M}}(K_n)}(S,T)\ge\max\{a,b\}.

For the reverse inequality, write A={x1,…,xa}A=\{x_1,\ldots,x_a\} and B={y1,…,yb}B=\{y_1,\ldots,y_b\}, and let r=min⁡{a,b}r=\min\{a,b\}. For each 1≤i≤r1\le i\le r, slide the token from xix_i to yiy_i. These moves are admissible because every two distinct vertices of KnK_n are adjacent. After these rr moves, if a>ba>b, delete the remaining vertices xr+1,…,xax_{r+1},\ldots,x_a; if b>ab>a, add the remaining vertices yr+1,…,yby_{r+1},\ldots,y_b. All intermediate configurations are feasible because every subset of V(Kn)V(K_n) is mutually visible. The resulting STST-path has length r+∣a−b∣=max⁡{a,b}r+|a-b|=\max\{a,b\}. Consequently, dRM(Kn)(S,T)=max⁡{∣S∖T∣,∣T∖S∣}d_{\mathcal{R}_{\mathcal{M}}(K_n)}(S,T)=\max\{|S\setminus T|,|T\setminus S|\}, proving (4).

We now determine the eccentricity of every configuration. Fix S⊆V(Kn)S\subseteq V(K_n) with ∣S∣=k|S|=k. For every configuration T⊆V(Kn)T\subseteq V(K_n), we have ∣S∖T∣≤k|S\setminus T|\le k and ∣T∖S∣≤n−k|T\setminus S|\le n-k. Thus, by (4), dRM(Kn)(S,T)≤max⁡{k,n−k}d_{\mathcal{R}_{\mathcal{M}}(K_n)}(S,T)\le\max\{k,n-k\}. The complement T=V(Kn)∖ST=V(K_n)\setminus S attains this bound, since ∣S∖T∣=k|S\setminus T|=k and ∣T∖S∣=n−k|T\setminus S|=n-k. Therefore, ecc⁡RM(Kn)(S)=max⁡{k,n−k}\operatorname{ecc}_{\mathcal{R}_{\mathcal{M}}(K_n)}(S)=\max\{k,n-k\}.

The maximum eccentricity is nn, attained exactly for k∈{0,n}k\in\{0,n\}. Moreover, the configurations ∅\varnothing and V(Kn)V(K_n) are at distance nn by (4). Hence, diam⁡(RM(Kn))=n\operatorname{diam}(\mathcal{R}_{\mathcal{M}}(K_n))=n, proving (5).

For the radius and center, minimize max⁡{k,n−k}\max\{k,n-k\} over 0≤k≤n0\le k\le n. Since k+(n−k)=nk+(n-k)=n, this maximum is at least ⌈n/2⌉\lceil n/2\rceil. If nn is even, equality holds precisely when k=n/2k=n/2. If nn is odd, equality holds precisely when k=(n−1)/2k=(n-1)/2 or k=(n+1)/2k=(n+1)/2. Consequently, rad⁡(RM(Kn))=⌈n/2⌉\operatorname{rad}(\mathcal{R}_{M}(K_n))=\lceil n/2\rceil, and the center consists exactly of the configurations of cardinality ⌊n/2⌋\lfloor n/2\rfloor or ⌈n/2⌉\lceil n/2\rceil. This proves (6) and (7). Finally, Theorem 3.6 gives (8). □\square

Figure 2 illustrates the structural description in the case n=4n=4. The gray TAR edges form Q4Q_4. The colored edges represent TS moves within the nontrivial cardinality layers: the green and blue edges induce copies of K4K_4 in RM1(K4)\mathcal{R}_{M}^{1}(K_4) and RM3(K4)\mathcal{R}_{M}^{3}(K_4), respectively, while the orange edges induce the Johnson graph J(4,2)J(4,2) in RM2(K4)\mathcal{R}_{M}^{2}(K_4).

The reconfiguration graph $\mathcal{R}_{M}(K_4)$

Figure 2. The reconfiguration graph RM(K4)\mathcal{R}_{M}(K_4). The gray edges are TAR edges joining configurations in consecutive cardinality layers. The blue, orange, and green edges are the TS edges within the layers RM3(K4)\mathcal{R}_{M}^{3}(K_4), RM2(K4)\mathcal{R}_{M}^{2}(K_4), and RM1(K4)\mathcal{R}_{M}^{1}(K_4), respectively. In particular, RM2(K4)≅J(4,2)\mathcal{R}_{M}^{2}(K_4)\cong J(4,2), whereas RM1(K4)≅RM3(K4)≅K4\mathcal{R}_{M}^{1}(K_4)\cong\mathcal{R}_{M}^{3}(K_4)\cong K_4.

Disconnected host graphs

We now allow disconnected hosts. Let G1,…,GcG_1,\ldots,G_c be the connected components of GG, and write μi=μ(Gi)\mu_i=\mu(G_i). A mutual-visibility set cannot meet distinct components, since no geodesic joins them. We say that a configuration SS is supported in a subgraph HH of GG if S⊆V(H)S\subseteq V(H). Thus, every nonempty configuration is supported in a unique component of GG. We regard each RM(Gi)\mathcal{R}_{M}(G_i) as its natural copy in RM(G)\mathcal{R}_{M}(G). These copies share the empty configuration and are otherwise pairwise disjoint.

For graphs H1,…,HtH_1,\ldots,H_t, we denote their disjoint union by ⋃i=1tHi\mathop{\bigcup}\limits_{i=1}^{t} H_i. This takes vertex-disjoint copies of the HiH_i with no edges between copies.

Proposition 3.8 (Decomposition by components). Let GG be a graph with connected components G1,…,GcG_1,\ldots,G_c, where c≥1c \ge1, and put μi=μ(Gi)\mu_i = \mu(G_i). Then μ(G)=max⁡1≤i≤cμi\mu(G) = \max_{1 \le i \le c} \mu_i. For every integer kk with 1≤k≤μ(G)1 \le k \le\mu(G),

RMk(G)≅⋃1≤i≤ck≤μiRMk(Gi).\mathcal{R}_{M}^{k}(G) \cong\mathop{\bigcup}\limits_{\substack{1 \le i \le c \\ k \le\mu_i}} \mathcal{R}_{M}^{k}(G_i).

For k=0k = 0, the layer RM0(G)\mathcal{R}_{M}^{0}(G) consists of the single vertex ∅\varnothing. Furthermore, RM(G)=⋃i=1cRM(Gi)\mathcal{R}_{M}(G) = \bigcup_{i=1}^{c} \mathcal{R}_{M}(G_i), with RM(Gi)∩RM(Gj)={∅}\mathcal{R}_{M}(G_i) \cap\mathcal{R}_{M}(G_j) = \{\varnothing\} for i≠ji \ne j. Equivalently, RM(G)\mathcal{R}_{M}(G) is obtained by identifying the empty configurations of the graphs RM(Gi)\mathcal{R}_{M}(G_i) into a single vertex. If c≥2c \ge2, then ∅\varnothing is a cut vertex and κ(RM(G))=1\kappa(\mathcal{R}_{M}(G)) = 1. Moreover, if c≥2c \ge2 and the components are relabeled so that μ1≥μ2≥⋯≥μc\mu_1 \ge\mu_2 \ge\cdots\ge\mu_c, then diam⁡(RM(G))=max⁡{D,μ1+μ2}\operatorname{diam}(\mathcal{R}_{M}(G)) = \max\{D, \mu_1 + \mu_2\}, where D=max⁡1≤i≤c{diam⁡(RM(Gi))}D = \max_{1 \le i \le c}\{\operatorname{diam}(\mathcal{R}_{M}(G_i))\}.

Proof: Every nonempty mutual-visibility set of GG belongs to exactly one M(Gi)\mathcal{M}(G_i). Conversely, M(Gi)⊆M(G)\mathcal{M}(G_i) \subseteq\mathcal{M}(G). Therefore, μ(G)=max⁡1≤i≤cμi\mu(G) = \max_{1 \le i \le c}\mu_i. The assertion for k=0k = 0 is immediate.

Let k≥1k \ge1 and S∈Mk(Gi)S \in\mathcal{M}_k(G_i). A TS move replaces x∈Sx \in S by an unoccupied neighbor yy. Since xy∈E(G)xy \in E(G), y∈V(Gi)y \in V(G_i). Thus, the resulting configuration still belongs to Mk(Gi)\mathcal{M}_k(G_i). TS adjacency within V(Gi)V(G_i) agrees in GiG_i and GG. Consequently, RMk(G)\mathcal{R}_{M}^{k}(G) is the disjoint union of the graphs RMk(Gi)\mathcal{R}_{M}^{k}(G_i) for which k≤μik \le\mu_i.

A TAR move whose two endpoints are nonempty also preserves the host component supporting the configuration. Removals leave the remaining tokens in that component; additions outside it violate mutual visibility. Hence, any reconfiguration sequence between nonempty configurations contained in different components of GG must pass through ∅\varnothing. Thus the copies RM(Gi)\mathcal{R}_{M}(G_i) meet only at ∅\varnothing. If c≥2c \ge2, deleting ∅\varnothing separates the nonempty configurations supported in different components and hence κ(RM(G))=1\kappa(\mathcal{R}_{M}(G)) = 1.

Now let SS and TT be supported in different components. Every STST-path passes through ∅\varnothing, and Proposition 3.3 gives dRM(G)(S,T)=dRM(G)(S,∅)+dRM(G)(∅,T)=∣S∣+∣T∣d_{\mathcal{R}_{M}(G)}(S,T) = d_{\mathcal{R}_{M}(G)}(S,\varnothing) + d_{\mathcal{R}_{M}(G)}(\varnothing,T) = |S| + |T|. The maximum distance across summands is μ1+μ2\mu_1 + \mu_2; within the ii-th summand it is diam⁡(RM(Gi))\operatorname{diam}(\mathcal{R}_{M}(G_i)). Maximizing gives the formula.

Isometric and convex subgraphs

Passing to an induced subgraph need not preserve mutual visibility: vertex deletion may alter distances and witnessing geodesics. A subgraph HH of GG is convex if every geodesic in GG between two vertices of HH is entirely contained in HH. In particular, every convex subgraph is isometric.

We recall the following results on convex subgraphs.

Lemma 3.9 (Di Stefano [5]). Let HH be a convex subgraph of GG, and let S⊆V(G)S \subseteq V(G) be a mutual-visibility set of GG. Then S∩V(H)S \cap V(H) is a mutual-visibility set of HH.

Lemma 3.9 is also stated by Bujtás et al. [2], who credit Di Stefano; both sources state the same restriction property.

Lemma 3.10 (Di Stefano [5]). Let HH be a convex subgraph of a graph GG. Then μ(H)≤μ(G)\mu(H) \le\mu(G).

We extend the feasible-set inclusion to isometric subgraphs and describe induced embeddings of the full reconfiguration graph and its layers.

Theorem 3.11 (Isometric embeddings). Let GG be a graph and let HH be an isometric subgraph of GG. Then, M(H)⊆M(G)\mathcal{M}(H) \subseteq\mathcal{M}(G) and the natural inclusion gives an isomorphism from RM(H)\mathcal{R}_{\mathcal{M}}(H) onto the subgraph of RM(G)\mathcal{R}_{\mathcal{M}}(G) induced by M(H)\mathcal{M}(H). The same conclusion holds for every fixed-cardinality layer.

Proof: Let S∈M(H)S \in\mathcal{M}(H). For every u,v∈Su,v \in S, there is a uvuv-geodesic in HH whose internal vertices avoid SS. Since HH is isometric, this path is also a geodesic in GG and hence S∈M(G)S \in\mathcal{M}(G).

It remains to compare adjacency. TAR adjacency depends only on symmetric difference, so is preserved in both directions. TS adjacency from RM(H)\mathcal{R}_{\mathcal{M}}(H) to RM(G)\mathcal{R}_{\mathcal{M}}(G) is preserved because E(H)⊆E(G)E(H) \subseteq E(G). Conversely, every isometric subgraph is induced: if x,y∈V(H)x,y \in V(H) and xy∈E(G)xy \in E(G), then dG(x,y)=1=dH(x,y)d_G(x,y)=1=d_H(x,y) and therefore xy∈E(H)xy \in E(H). Hence, every TS edge of RM(G)\mathcal{R}_{\mathcal{M}}(G) with both endpoints in M(H)\mathcal{M}(H) is also present in RM(H)\mathcal{R}_{\mathcal{M}}(H). Thus the image is an induced subgraph. Restricting to cardinality kk proves the layer statement. □\square

Configurations of GG supported in HH need not belong to M(H)\mathcal{M}(H). Isometry guarantees that distances agree, but it does not imply that every geodesic of GG with endpoints in HH lies in HH. Convexity rules out this phenomenon and yields equality.

Corollary 3.12 (Convex subgraphs). If HH is a convex subgraph of GG, then M(H)={S∈M(G):S⊆V(H)}\mathcal{M}(H)=\{S \in\mathcal{M}(G): S \subseteq V(H)\}. Consequently, RM(H)\mathcal{R}_{\mathcal{M}}(H) is precisely the subgraph of RM(G)\mathcal{R}_{\mathcal{M}}(G) induced by the configurations supported in HH.

Proof: A convex subgraph is isometric, so Theorem 3.11 gives one inclusion. Conversely, let S∈M(G)S \in\mathcal{M}(G) with S⊆V(H)S \subseteq V(H). Every geodesic in GG between vertices of HH is contained in HH. Thus the geodesics witnessing visibility for SS remain in HH and avoid the other vertices of SS. Thus, S∈M(H)S \in\mathcal{M}(H). □\square

Corollary 3.13 (Clique-boundary deletion). Let GG be a graph and let D⊊V(G)D \subsetneq V(G), with external boundary ∂D=NG(D)∖D\partial D=N_G(D)\setminus D. If ∂D\partial D induces a clique, then G−DG-D is convex in GG. Consequently, M(G−D)={S∈M(G):S∩D=∅}\mathcal{M}(G-D)=\{S \in\mathcal{M}(G): S \cap D=\varnothing\}, and RM(G−D)\mathcal{R}_{\mathcal{M}}(G-D) is the subgraph of RM(G)\mathcal{R}_{\mathcal{M}}(G) induced by the configurations that avoid DD.

Proof: Suppose that a geodesic with endpoints outside DD enters DD. Let xx and yy be the vertices immediately preceding and following a maximal subpath contained in DD. Then, x,y∈∂Dx,y \in\partial D. Since ∂D\partial D is a clique, replacing this subpath with the edge xyxy produces a shorter path. Hence every geodesic between vertices of G−DG-D stays there. Thus, G−DG-D is convex, and the conclusion follows from Corollary 3.12. □\square

When D={v}D=\{v\}, this is the simplicial-vertex case, since ∂D=NG(v)\partial D=N_G(v) is a clique. The fact that RMk(H)\mathcal{R}_{\mathcal{M}}^k(H) is an induced subgraph of RMk(G)\mathcal{R}_{\mathcal{M}}^k(G) does not imply that distinct components remain disconnected in the larger layer: paths in RMk(G)\mathcal{R}_{\mathcal{M}}^k(G) may leave and reenter the copy. We next study layers of complete bipartite graphs. In this family, mutual visibility is determined by the number of selected vertices in each partite class.

Complete bipartite graphs

Let G=Km,nG=K_{m,n} have bipartition A∪BA \cup B, where ∣A∣=m|A|=m and ∣B∣=n|B|=n. For S⊆V(G)S \subseteq V(G), we say that SS is of type (a,b)(a,b) if a=∣S∩A∣a=|S \cap A| and b=∣S∩B∣b=|S \cap B|. The extremal value is known.

Theorem 4.1 [5]. Let G=Km,nG = K_{m,n} be a complete bipartite graph with m,n≥3m,n \ge3. Then μ(G)=m+n−2\mu(G) = m + n - 2.

The feasible configurations of Km,nK_{m,n} follow directly from its length-two geodesics. For the balanced case, Bujtás et al. [2] give an equivalent case description in the proof of their visibility-polynomial formula; they also note that the unbalanced case can be treated similarly. We state the conditions uniformly for m,n≥2m,n \ge2 because they identify the feasible levels used in the layer results below.

Theorem 4.2 (Set characterization). Let m,n≥2m,n \ge2, and let A,BA,B be the partite classes of Km,nK_{m,n}, with ∣A∣=m|A| = m and ∣B∣=n|B| = n. A set S⊆V(Km,n)S \subseteq V(K_{m,n}) of type (a,b)(a,b), where a=∣S∩A∣a = |S \cap A| and b=∣S∩B∣b = |S \cap B|, is a mutual-visibility set if and only if the following conditions hold:

(i) a≤1a \le1 or b<nb < n, and

(ii) b≤1b \le1 or a<ma < m.

Proof: Assume first that a≥2a \ge2. Any two vertices of S∩AS \cap A are at distance two, and every geodesic joining them has its internal vertex in BB. Thus any such pair is mutually visible if and only if B∖S≠∅B \setminus S \ne\varnothing, that is, b<nb < n. This proves the first condition. By symmetry, if b≥2b \ge2, then the vertices of S∩BS \cap B are pairwise mutually visible if and only if a<ma < m. Vertices in different partite classes are adjacent, imposing no further restriction. The conditions are therefore necessary and sufficient. □

A mutual-visibility set SS is maximal if no proper superset is mutually visible. It is maximum if ∣S∣=μ(G)|S| = \mu(G). Maximum sets are maximal, but the converse may fail. The proof of Brešar and Yero [1] considers the same patterns of maximal mutual-visibility sets. We record them explicitly in type notation.

Corollary 4.3 (Maximal sets). Let m,n≥3m,n \ge3. A mutual-visibility set of Km,nK_{m,n} is maximal if and only if it is of type (m−1,n−1)(m - 1,n - 1), (m,1)(m,1) or (1,n)(1,n).

Proof: Adding either of the two omitted vertices to a set of type (m−1,n−1)(m - 1,n - 1) fills one partite class while the other contains at least two tokens. A set of type (m,1)(m,1) cannot receive another vertex of BB, and the case (1,n)(1,n) is symmetric. Hence all three types are maximal.

Conversely, let SS be maximal. Assume first that a<ma < m and b<nb < n. If a≤m−2a \le m - 2, a vertex of A∖SA \setminus S may be added while both partite classes remain incomplete, contrary to maximality. Hence a=m−1a = m - 1, and, by symmetry, b=n−1b = n - 1. If b=nb = n, Theorem 4.2 gives a≤1a \le1, and maximality then gives a=1a = 1. The case a=ma = m similarly gives b=1b = 1. □

Thus, maximal mutual-visibility sets need not be maximum. For instance, a set of type (1,5)(1,5) in K4,5K_{4,5} is maximal and has cardinality 6<μ(K4,5)=76 < \mu(K_{4,5}) = 7.

For a statement P\mathcal{P}, write 1P=11_{\mathcal{P}} = 1 if P\mathcal{P} is true and 00 otherwise.

Corollary 4.4 (Enumeration). For m,n≥2m,n \ge2 and 0≤k≤m+n0 \le k \le m+n, the number rk=∣Mk(Km,n)∣r_k = |\mathcal{M}_k(K_{m,n})| is

rk=(m+nk)−12≤k−n≤m(mk−n)−12≤k−m≤n(nk−m)+1k=m+n.r_k = \binom{m+n}{k} - 1_{2 \le k-n \le m}\binom{m}{k-n} - 1_{2 \le k-m \le n}\binom{n}{k-m} + 1_{k=m+n}.

Proof: Fix kk. By Theorem 4.2, the nonfeasible kk-subsets are the union of two families: FB\mathcal{F}_B, consisting of those containing BB and at least two vertices of AA, and FA\mathcal{F}_A, defined symmetrically. A set in FB\mathcal{F}_B is obtained by choosing k−nk-n vertices from AA, provided 2≤k−n≤m2 \le k-n \le m. Thus, ∣FB∣=12≤k−n≤m(mk−n)|\mathcal{F}_B|=\mathbf{1}_{2\le k-n\le m}\binom{m}{k-n}. Similarly, ∣FA∣=12≤k−m≤n(nk−m)|\mathcal{F}_A|=\mathbf{1}_{2\le k-m\le n}\binom{n}{k-m}.

The intersection contains only A∪BA\cup B when k=m+nk=m+n and is empty otherwise. Hence ∣FA∩FB∣=1k=m+n|\mathcal{F}_A\cap\mathcal{F}_B|=\mathbf{1}_{k=m+n}. Applying inclusion-exclusion to the (m+nk)\binom{m+n}{k} subsets gives the formula.

For the remainder of this section, assume that m,n≥3m,n\ge3. Then Theorem 4.1 gives μ(Km,n)=m+n−2\mu(K_{m,n})=m+n-2. In particular, the number of maximum mutual-visibility sets is

∣Mm+n−2(Km,n)∣={mn,if m,n≥4,3n+3,if m=3 and m<n,3m+3,if n=3 and n<m,15,if m=n=3.|\mathcal{M}_{m+n-2}(K_{m,n})|= \begin{cases} mn, & \text{if }m,n\ge4,\\ 3n+3, & \text{if }m=3\text{ and }m<n,\\ 3m+3, & \text{if }n=3\text{ and }n<m,\\ 15, & \text{if }m=n=3. \end{cases}

For a fixed integer 0≤k≤μ(Km,n)0\le k\le\mu(K_{m,n}), consider the integer interval Jk=[max⁡{0,k−n},min⁡{m,k}]J_k=[\max\{0,k-n\},\min\{m,k\}]. A kk-element subset S⊆V(Km,n)S\subseteq V(K_{m,n}) of type (a,b)(a,b) satisfies b=k−ab=k-a. The bounds 0≤a≤m0\le a\le m and 0≤k−a≤n0\le k-a\le n show that JkJ_k is precisely the interval of values of aa allowed by the cardinality constraints, before imposing mutual visibility.

By Theorem 4.2, such a set fails to be a mutual-visibility set precisely when b=nb=n and a≥2a\ge2, or when a=ma=m and b≥2b\ge2. The first case excludes the lower endpoint a=k−na=k-n when k−n≥2k-n\ge2. The second excludes the upper endpoint a=ma=m when k−m≥2k-m\ge2. No other values are excluded. Therefore, the feasible values form an integer interval, which we denote by IkI_k. Thus, Ik={∣S∩A∣:S∈Mk(Km,n)}I_k=\{|S\cap A|:S\in\mathcal{M}_k(K_{m,n})\}. Every i∈Iki\in I_k is realized by a mutual-visibility set: choose X⊆AX\subseteq A and Y⊆BY\subseteq B with ∣X∣=i|X|=i and ∣Y∣=k−i|Y|=k-i. The bounds of JkJ_k guarantee these choices. The type (i,k−i)(i,k-i) avoids the excluded endpoints, so Theorem 4.2 gives X∪Y∈Mk(Km,n)X\cup Y\in\mathcal{M}_k(K_{m,n}).

For i∈Iki\in I_k, the configurations with ∣S∩A∣=i|S\cap A|=i form level ii of RMk(Km,n)\mathcal{R}^k_{\mathcal{M}}(K_{m,n}). Every configuration at level ii is of type (i,k−i)(i,k-i), and the construction above shows that this level is nonempty. For two consecutive levels qq and q+1q+1, we call qq the lower level and q+1q+1 the upper level.

Lemma 4.5 (Two consecutive levels). Let m,n≥3m,n\ge3 and 0≤k≤m+n−20\le k\le m+n-2. Suppose that q,q+1∈Ikq,q+1\in I_k. The subgraph of RMk(Km,n)\mathcal{R}^k_{\mathcal{M}}(K_{m,n}) induced by the configurations at levels qq and q+1q+1 is connected.

Proof: For a configuration SS at level qq, write S=X∪YS=X\cup Y, where X=S∩AX=S\cap A and Y=S∩BY=S\cap B. Since q,q+1∈Ikq,q+1\in I_k, we have q<mq<m and 1≤k−q≤n1\le k-q\le n. Thus, both A∖XA\setminus X and YY are nonempty.

To replace x∈Xx\in X by x′∈A∖Xx'\in A\setminus X, choose y∈Yy\in Y and slide first from yy to x′x' and then from xx to yy. Likewise, to replace y∈Yy\in Y by y′∈B∖Yy'\in B\setminus Y, choose x′∈A∖Xx'\in A\setminus X and first slide the token at yy to x′x', and then slide the token at xx to y′y'. Each intermediate configuration is at level q+1q+1, and each final configuration is at level qq. Both levels are feasible, and all destinations are unoccupied, so the slides are admissible.

Configurations at level qq have equal cardinalities in each part, so successive within-part exchanges transform any one into any other. Hence any two configurations at level qq can be connected by a walk using only levels qq and q+1q+1.

Finally, every configuration at level q+1q+1 contains a token in AA and has k−q−1<nk-q-1<n tokens in BB. Sliding one of these tokens to an unoccupied vertex of BB produces a configuration at level qq. Hence, the subgraph induced by the two levels is connected.

Theorem 4.6 (Connectivity of the layers). Let m,n≥3m,n \ge3 and 0≤k≤m+n−20 \le k \le m+n-2. If k<m+n−2k < m+n-2, then RMk(Km,n)\mathcal{R}_{\mathcal{M}}^{k}(K_{m,n}) is connected. The maximum layer RMm+n−2(Km,n)\mathcal{R}_{\mathcal{M}}^{m+n-2}(K_{m,n}) is connected if and only if min⁡{m,n}=3\min\{m,n\}=3. If m,n≥4m,n \ge4, this layer consists of mnmn isolated vertices.

Proof: The layer RM0(Km,n)\mathcal{R}_{\mathcal{M}}^{0}(K_{m,n}) has one vertex. Let 1≤k≤m+n−31 \le k \le m+n-3. Recall that IkI_k is obtained from JkJ_k by imposing mutual visibility.

We first show that IkI_k has at least two elements. If k≤2k \le2, neither exclusion condition k−n≥2k-n \ge2 nor k−m≥2k-m \ge2 holds, so Ik=Jk=[0,k]I_k=J_k=[0,k]. If k≥3k \ge3, then ∣Jk∣=min⁡{m,k}−max⁡{0,k−n}+1=min⁡{k,m,n,m+n−k}+1≥4|J_k|=\min\{m,k\}-\max\{0,k-n\}+1=\min\{k,m,n,m+n-k\}+1 \ge4. Only the lower endpoint with k−n≥2k-n \ge2 and the upper with k−m≥2k-m \ge2 are excluded. Thus, at most two elements are removed, so at least two consecutive feasible values remain. By Lemma 4.5, every pair of consecutive levels in IkI_k induces a connected subgraph. Successive such subgraphs share a nonempty level. Since IkI_k is an integer interval, their union is the whole layer RMk(Km,n)\mathcal{R}_{\mathcal{M}}^{k}(K_{m,n}), which is therefore connected.

Now let k=m+n−2k=m+n-2. If m,n≥4m,n \ge4, Theorem 4.2 implies that the only feasible type is (m−1,n−1)(m-1,n-1). A token slide would produce type (m−2,n)(m-2,n) or (m,n−2)(m,n-2), neither of which is feasible. Hence, no admissible token slide is possible. There are mnmn such configurations, one for every choice of an omitted vertex from each part. Thus, the maximum layer consists of mnmn isolated vertices.

Finally, suppose that min⁡{m,n}=3\min\{m,n\}=3. By symmetry, assume m=3m=3. If n>3n>3, the feasible types are (1,n)(1,n) and (2,n−1)(2,n-1), so Ik={1,2}I_k=\{1,2\}. If n=3n=3, the feasible types are (1,3)(1,3), (2,2)(2,2) and (3,1)(3,1), so Ik={1,2,3}I_k=\{1,2,3\}. In both cases, Lemma 4.5 connects the consecutive levels and hence the entire maximum layer.

Lemma 4.5 also bounds distances in connected layers using TS moves.

Proposition 4.7 (Distance bound within a connected layer). Let m,n≥3m,n \ge3 and 0≤k≤m+n−20 \le k \le m+n-2. Assume that either k<m+n−2k<m+n-2, or k=m+n−2k=m+n-2 and min⁡{m,n}=3\min\{m,n\}=3. Then, for all S,T∈Mk(Km,n)S,T \in\mathcal{M}_k(K_{m,n}), we have dRMk(Km,n)(S,T)≤∣S△T∣−∣aS−aT∣d_{\mathcal{R}_{\mathcal{M}}^{k}(K_{m,n})}(S,T)\le|S\mathbin{\triangle}T|-|a_S-a_T|, where aS=∣S∩A∣a_S=|S\cap A| and aT=∣T∩A∣a_T=|T\cap A|. In particular, dRMk(Km,n)(S,T)≤∣S△T∣d_{\mathcal{R}_{\mathcal{M}}^{k}(K_{m,n})}(S,T)\le|S\mathbin{\triangle}T|. Consequently, diam⁡(RMk(Km,n))≤2min⁡{k,m+n−k}\operatorname{diam}(\mathcal{R}_{\mathcal{M}}^{k}(K_{m,n}))\le2\min\{k,m+n-k\}.

Proof: The assertion is immediate when S=TS=T. Set h=∣S△T∣/2h=|S\mathbin{\triangle}T|/2 and d=∣aS−aT∣d=|a_S-a_T|. Perform dd TS moves. At each step, if the current configuration has type (a,k−a)(a,k-a) with a>aTa>a_T, move a token from a selected vertex in A∖TA\setminus T to an unoccupied vertex of T∩BT\cap B; when a<aTa<a_T, interchange AA and BB. The required vertices exist because the current configuration has more selected vertices than TT in the source part and fewer in the destination part. Each move changes the first coordinate by one toward aTa_T, keeping it between aSa_S and aTa_T. Since IkI_k is an interval, every intermediate configuration is feasible.

After dd slides, the type is (aT,k−aT)(a_T,k-a_T), leaving only within-part exchanges. If discrepancies remain, Theorem 4.6 and its proof give ∣Ik∣≥2|I_k|\ge2. Since this integer interval has at least two elements, each feasible value has an adjacent feasible value, so the current level has an adjacent feasible level. Lemma 4.5 realizes each exchange in two slides through that level. The remaining h−dh-d exchanges give total length at most d+2(h−d)=2h−d=∣S△T∣−dd+2(h-d)=2h-d=|S\mathbin{\triangle}T|-d. Finally, two kk-subsets of an (m+n)(m+n)-set differ in at most 2min⁡{k,m+n−k}2\min\{k,m+n-k\}.

The following corollary recovers the case m,n≥3m,n\ge3 of the formula for complete bipartite graphs proved by Dettlaff et al. [4]. We give a proof from layer connectivity and the component criterion.

Corollary 4.8 [4]. For m,n≥3m,n \ge3, we have

Mob⁡μ(Km,n)={m+n−2,if min⁡{m,n}=3,m+n−3,if m,n≥4.\operatorname{Mob}_{\mu}(K_{m,n}) = \begin{cases} m+n-2, & \text{if }\min\{m,n\}=3,\\ m+n-3, & \text{if }m,n\ge4. \end{cases}

Proof. Assume first that min⁡{m,n}=3\min\{m,n\}=3. The maximum layer is connected, and its configurations together cover both partite classes. It follows from Corollary 2.4 that Mob⁡μ(Km,n)=μ(Km,n)=m+n−2\operatorname{Mob}_{\mu}(K_{m,n})=\mu(K_{m,n})=m+n-2. Now assume that m,n≥4m,n\ge4. Every maximum configuration is isolated and omits one vertex from each partite class; hence, no maximum set is mobile. On the other hand, the layer of size m+n−3m+n-3 is connected. Its configurations cover V(Km,n)V(K_{m,n}): every vertex belongs, for example, to a configuration of type (m−1,n−2)(m-1,n-2). By Corollary 2.4, these configurations are mobile. Consequently, Mob⁡μ(Km,n)=m+n−3\operatorname{Mob}_{\mu}(K_{m,n})=m+n-3.

The preceding characterization also yields formulas for two other mutual-visibility parameters. For comparison, we first recall the mutual-visibility polynomial in the balanced case.

Proposition 4.9 [2]. For n≥3n\ge3, the complete bipartite graph Kn,nK_{n,n} has visibility polynomial PKn,n(z)=((1+z)n−zn)2+2nzn+1+2znP_{K_{n,n}}(z)=\left((1+z)^n-z^n\right)^2+2nz^{n+1}+2z^n.

We now extend this polynomial formula to arbitrary m,n≥2m,n\ge2.

Corollary 4.10 (Visibility polynomial of Km,nK_{m,n}). Let m,n≥2m,n\ge2. The visibility polynomial of Km,nK_{m,n} is PKm,n(z)=(1+z)m+n−zn((1+z)m−1−mz)−zm((1+z)n−1−nz)+zm+nP_{K_{m,n}}(z)=(1+z)^{m+n}-z^n\left((1+z)^m-1-mz\right)-z^m\left((1+z)^n-1-nz\right)+z^{m+n}.

Proof. Multiply the formula in Corollary 4.4 by zkz^k and sum over 0≤k≤m+n0\le k\le m+n. The first term sums to (1+z)m+n(1+z)^{m+n}. For the first correction term, the binomial theorem gives ∑k=n+2m+n(mk−n)zk=zn∑j=2m(mj)zj=zn((1+z)m−1−mz)\sum_{k=n+2}^{m+n}\binom{m}{k-n}z^k=z^n\sum_{j=2}^{m}\binom{m}{j}z^j=z^n\left((1+z)^m-1-mz\right). The second correction term follows by interchanging mm and nn, and the intersection term contributes zm+nz^{m+n}. This proves the formula.

For m=n≥3m=n\ge3, Corollary 4.10 simplifies to Proposition 4.9. Bujtás et al. [2] observe that the general complete bipartite case can be handled similarly, but do not state an explicit formula. Corollary 4.10 makes the general formula explicit.

Recall that the lower mutual-visibility number μ−(G)\mu^{-}(G) is the minimum cardinality of a maximal mutual-visibility set of GG [1].

Corollary 4.11 [1 Proposition 6]. Let m,n≥3m,n\ge3. Then, we have μ−(Km,n)=min⁡{m,n}+1\mu^{-}(K_{m,n})=\min\{m,n\}+1.

Proof. Corollary 4.3 gives the maximal types (m−1,n−1)(m-1,n-1), (m,1)(m,1) and (1,n)(1,n). Their cardinalities are m+n−2m+n-2, m+1m+1 and n+1n+1, respectively. Since m,n≥3m,n\ge3, the minimum of these three numbers is min⁡{m,n}+1\min\{m,n\}+1.

Theorem 4.6 and Proposition 4.7 give the main reconfiguration results for Km,nK_{m,n}. The type characterization supplies their feasible levels, while the counting formulas complement earlier visibility results. For trees, branching vertices can also disconnect intermediate layers.

Trees

Let TT be a tree with leaf set L(T)L(T). A branching vertex has degree at least three. For every nonempty set S⊆V(T)S \subseteq V(T), let HT(S)H_T(S) be the unique minimal subtree of TT containing SS. We recall the following characterization, writing HT(S)H_T(S) for the Steiner subtree used in the source.

Lemma 5.1 [14]. Let TT be a tree and let S⊆V(T)S \subseteq V(T) with ∣S∣≥2|S| \ge2. Then SS is a mutual-visibility set of TT if and only if SS is precisely the leaf set L(HT(S))L(H_T(S)).

We also recall the extremal value for trees.

Corollary 5.2 [5]. Let TT be a tree with at least two vertices. Then L(T)L(T) is a mutual-visibility set and μ(T)=∣L(T)∣\mu(T) = |L(T)|.

Branching vertices can obstruct connectivity in intermediate layers. Let pp be a vertex of degree r≥3r \ge3, and fix an ordering C1,…,CrC_1,\ldots,C_r of the components of T−pT-p. We call these components the branches of TT at pp. For S⊆V(T)∖{p}S \subseteq V(T) \setminus\{p\}, define the occupancy vector of SS at pp with respect to this ordering, as αp(S)=(∣S∩V(C1)∣,…,∣S∩V(Cr)∣)\alpha_p(S) = (|S \cap V(C_1)|,\ldots,|S \cap V(C_r)|). We say that the branch CiC_i is occupied by SS if S∩V(Ci)≠∅S \cap V(C_i) \ne\emptyset.

The next lemma shows that pp acts as a barrier whenever at least three branches are occupied: pp stays unoccupied and the occupancy vector is invariant.

Lemma 5.3 (Branch barrier). Let TT be a tree, let pp be a branching vertex, and let S∈Mk(T)S \in\mathcal{M}_k(T) with p∉Sp \notin S. Suppose that at least three coordinates of αp(S)\alpha_p(S) are positive. For S′∈Mk(T)S' \in\mathcal{M}_k(T), if S′S' belongs to the same connected component of RMk(T)R^k_{\mathcal{M}}(T) as SS, then p∉S′p \notin S' and αp(S′)=αp(S)\alpha_p(S') = \alpha_p(S).

Proof: No admissible TS move starting at SS can place a token on pp. Such a slide from x∈Sx \in S would give U=(S∖{x})∪{p}U = (S \setminus\{x\}) \cup\{p\}. Since at least three branches at pp are occupied by SS, there exist vertices u,v∈S∖{x}u,v \in S \setminus\{x\} in two distinct components of T−pT-p other than the component containing xx. The unique uvuv-path in TT contains pp as an internal vertex. Since u,v,p∈Uu,v,p \in U, uu and vv are not mutually visible in UU. Thus the slide is not admissible.

Every admissible slide therefore avoids pp. Its edge lies in one component CiC_i of T−pT-p. It moves a token within CiC_i, preserving the number of tokens in every component of T−pT-p. Hence it leaves pp unoccupied and preserves αp(S)\alpha_p(S).

In particular, at least three branches at pp remain occupied, so the same argument applies after each admissible slide. By induction on the slide sequence, every reachable configuration S′S' satisfies p∉S′p \notin S' and αp(S′)=αp(S)\alpha_p(S') = \alpha_p(S).

We next identify the branching vertices that satisfy the hypotheses of Lemma 5.3. Let S∈Mk(T)S \in\mathcal{M}_k(T) with k≥3k \ge3, and define its set of active branching vertices by

BT(S)={v∈V(HT(S)):deg⁡HT(S)(v)≥3}.B_T(S) = \{v \in V(H_T(S)) : \deg_{H_T(S)}(v) \ge3\}.

By Lemma 5.1, S=L(HT(S))S = L(H_T(S)), so S∩BT(S)=∅S \cap B_T(S) = \emptyset. It is nonempty because a tree with at least three leaves has a branching vertex. By minimality of HT(S)H_T(S), at least three branches at each b∈BT(S)b \in B_T(S) contain a vertex of SS. Thus Lemma 5.3 applies at every such vertex bb. For each s∈Ss \in S, let TsT_s be the component of T−BT(S)T-B_T(S) containing ss.

Lemma 5.4 (Pendant-branch structure). Let TT be a tree and let S∈Mk(T)S \in\mathcal{M}_k(T), where k≥3k \ge3. Let KK be the minimal subtree of TT containing BT(S)B_T(S). If BT(S)={b}B_T(S) = \{b\}, then KK consists of the single vertex bb. Every component of T−BT(S)T-B_T(S) contains at most one vertex of SS. Moreover, for each s∈Ss \in S, the component

TsT_s has a unique neighbor bs∈BT(S)b_s \in B_T(S), and HT(S)=K∪⋃s∈SPbssH_T(S)=K\cup\bigcup_{s\in S}P_{b_ss}, where PxyP_{xy} denotes the unique xyxy-path in TT. If we choose xs∈V(Ts)x_s\in V(T_s) for each s∈Ss\in S, and put X={xs:s∈S}X=\{x_s:s\in S\}, then

HT(X)=K∪⋃s∈SPbsxsandL(HT(X))=X.H_T(X)=K\cup\bigcup_{s\in S}P_{b_sx_s}\qquad\text{and}\qquad L(H_T(X))=X.

Proof: For three vertices of a tree, their median is the unique vertex that lies on each of the three pairwise paths. Here S=L(HT(S))S=L(H_T(S)) and BT(S)≠∅B_T(S)\ne\varnothing. Suppose that a component DD of T−BT(S)T-B_T(S) contains distinct vertices s,t∈Ss,t\in S, and choose u∈S∖{s,t}u\in S\setminus\{s,t\}. Let mm be the median of s,t,us,t,u. As distinct leaves of HT(S)H_T(S), none of s,t,us,t,u lies between the others. The three paths from mm therefore start with distinct edges, so deg⁡HT(S)(m)≥3\deg_{H_T(S)}(m)\ge3. On the other hand, mm lies on the stst-path, which is contained in DD. Thus m∈BT(S)∩V(D)m\in B_T(S)\cap V(D), a contradiction. Hence every component of T−BT(S)T-B_T(S) contains at most one vertex of SS.

Since TT is connected and BT(S)B_T(S) is nonempty, each TsT_s has at least one neighbor in BT(S)B_T(S). Suppose that it has distinct neighbors b,b′∈BT(S)b,b'\in B_T(S). The internal vertices of the bb′bb'-path lie in TsT_s, and this path is contained in HT(S)H_T(S). If ss lies on this path, then it is an internal vertex and cannot be a leaf of HT(S)H_T(S), a contradiction. Otherwise, let mm be the median of s,b,b′s,b,b'. Since TsT_s is connected and contains ss and the internal vertices of the bb′bb'-path, the path from ss to the bb′bb'-path meets it at a vertex m∈V(Ts)m\in V(T_s). The paths from mm to ss, bb, and b′b' start with three distinct edges of HT(S)H_T(S), so deg⁡HT(S)(m)≥3\deg_{H_T(S)}(m)\ge3. Thus m∈BT(S)∩V(Ts)m\in B_T(S)\cap V(T_s), again a contradiction. Hence TsT_s has a unique neighbor bs∈BT(S)b_s\in B_T(S).

Both KK and the paths PbssP_{b_ss} lie in HT(S)H_T(S). Their union is connected and contains SS. By the minimality of HT(S)H_T(S), we have HT(S)=K∪⋃s∈SPbssH_T(S)=K\cup\bigcup_{s\in S}P_{b_ss}.

Now choose xs∈V(Ts)x_s\in V(T_s) for every s∈Ss\in S and put X={xs:s∈S}X=\{x_s:s\in S\}. For each b∈BT(S)b\in B_T(S), the vertices ss and xsx_s lie in the same component of T−bT-b. Thus XX occupies exactly the same branches at bb as SS. In particular, every b∈BT(S)b\in B_T(S) still has degree at least three in HT(X)H_T(X), and hence K⊆HT(X)K\subseteq H_T(X). Since HT(X)H_T(X) contains both bsb_s and xsx_s, it also contains every path PbsxsP_{b_sx_s}. Conversely, this union is connected and contains XX. Therefore, HT(X)=K∪⋃s∈SPbsxsH_T(X)=K\cup\bigcup_{s\in S}P_{b_sx_s}. Each xsx_s is the endpoint of its corresponding pendant path, so X⊆L(HT(X))X\subseteq L(H_T(X)). By minimality, L(HT(X))⊆XL(H_T(X))\subseteq X, so L(HT(X))=XL(H_T(X))=X. □\square

Recall that the Cartesian product □i∈IGi\square_{i\in I}G_i has vertex set ∏i∈IV(Gi)\prod_{i\in I}V(G_i). Two tuples are adjacent if they differ in exactly one coordinate, along an edge of its factor GiG_i.

Theorem 5.5 (Active-branch decomposition). Let TT be a tree and let S∈Mk(T)S\in\mathcal{M}_k(T), where k>3k>3. Then the subtrees TsT_s, s∈Ss\in S, are pairwise vertex-disjoint. For each tuple (xs)s∈S(x_s)_{s\in S}, with xs∈V(Ts)x_s\in V(T_s) for every s∈Ss\in S, define φ((xs)s∈S)={xs:s∈S}\varphi((x_s)_{s\in S})=\{x_s:s\in S\}. The map φ\varphi is a graph isomorphism

□s∈STs≅Ck(S),\square_{s\in S}T_s\cong C_k(S),

where Ck(S)C_k(S) is the component of Rkm(T)\mathcal{R}_k^m(T) containing SS. Equivalently, a configuration belongs to Ck(S)C_k(S) if and only if it has exactly one token in each TsT_s and none outside these subtrees.

Proof: By Lemma 5.1, S=L(HT(S))S=L(H_T(S)). For b∈BT(S)b\in B_T(S), every component of HT(S)−bH_T(S)-b contains a leaf, so at least deg⁡HT(S)(b)≥3\deg_{H_T(S)}(b)\ge3 branches are occupied. By Lemma 5.3, BT(S)B_T(S) stays unoccupied along every walk from SS. Hence tokens cannot move between components of T−BT(S)T-B_T(S). By Lemma 5.4, the subtrees TsT_s are pairwise vertex-disjoint, each initially contains one token, and all other components are unoccupied. These properties are therefore invariant along every path in Ck(S)C_k(S).

Conversely, choose xs∈V(Ts)x_s \in V(T_s) for each s∈Ss \in S, and put X=φ((xs)s∈S)={xs:s∈S}X=\varphi((x_s)_{s\in S})=\{x_s:s\in S\}. Lemma 5.4 and Lemma 5.1 imply that XX is a mutual-visibility set. Move the token initially at ss to xsx_s along the unique path in TsT_s, processing the tokens one at a time. The intermediate configurations have this form and are feasible, so XX is reachable. Thus φ\varphi is well defined and surjective onto V(Ck(S))V(C_k(S)). It is injective since xsx_s is the unique vertex in X∩V(Ts)X\cap V(T_s). Adjacency means changing one coordinate along an edge of its subtree. Hence φ\varphi is a graph isomorphism.

Figure 3 illustrates the Cartesian-product decomposition. In panel (a), the branches C1,C2,C3C_1,C_2,C_3 contain 3, 1, and 2 vertices of SS, respectively, so αp(S)=(3,1,2)\alpha_p(S)=(3,1,2) in this ordering. Lemma 5.3 keeps pp unoccupied and αp(S)\alpha_p(S) invariant, preventing tokens from changing branches.

Cartesian-product decomposition of mutual-visibility configurations

Figure 3. (a) Branch occupancy at pp. (b) Pendant-branch decomposition. Red vertices form the mutual-visibility set SS, dashed regions mark the indicated components, and blue edges in (b) mark the pendant paths.

In panel (b), BT(S)={b1,b2}B_T(S)=\{b_1,b_2\}. Deleting them leaves four occupied components TsiT_{s_i} with S∩V(Tsi)={si}S\cap V(T_{s_i})=\{s_i\}, 1≤i≤41\le i\le4, and the unoccupied central vertex. The core KK is the path joining b1b2b_1b_2-path, and HT(S)H_T(S) consists of KK together with the pendant paths PbisiP_{b_is_i}. The component consists of the configurations {xs1,xs2,xs3,xs4}\{x_{s_1},x_{s_2},x_{s_3},x_{s_4}\} with xsi∈V(Tsi)x_{s_i}\in V(T_{s_i}). An admissible token slide changes one coordinate along an edge of its subtree, giving Ck(S)≅Ts1□Ts2□Ts3□Ts4C_k(S)\cong T_{s_1}\square T_{s_2}\square T_{s_3}\square T_{s_4}.

The decomposition also gives the basic parameters of each component. Recall that a connected graph is a median graph if every three vertices have a unique vertex lying on a shortest path between each pair.

Corollary 5.6. Under the hypotheses of Theorem 5.5, put ns=∣V(Ts)∣n_s=|V(T_s)| and ms=∣E(Ts)∣m_s=|E(T_s)|. Then

∣V(Ck(S))∣=∏s∈Sns,∣E(Ck(S))∣=∑s∈Sms∏t∈S∖{s}nt,and diam⁡(Ck(S))=∑s∈Sdiam⁡(Ts).\begin{aligned} |V(C_k(S))|&=\prod_{s\in S}n_s,\qquad|E(C_k(S))|=\sum_{s\in S}m_s\prod_{t\in S\setminus\{s\}}n_t,\\ \text{and }\operatorname{diam}(C_k(S))&=\sum_{s\in S}\operatorname{diam}(T_s). \end{aligned}

Moreover, Ck(S)C_k(S) is a median graph and hence a partial cube.

Proof. Each vertex of the product is a tuple containing one vertex from each factor TsT_s. Each edge chooses an edge in one factor and vertices in the others, proving the counts. The product distance between tuples x=(xs)x=(x_s) and y=(ys)y=(y_s) is ∑s∈SdTs(xs,ys)\sum_{s\in S}d_{T_s}(x_s,y_s): each move changes one coordinate, and following shortest paths in successive factors attains the bound. Choosing xs,ysx_s,y_s at distance diam⁡(Ts)\operatorname{diam}(T_s) in each factor gives the diameter formula. The median of three product vertices is obtained by taking the tree median in each coordinate. Thus Ck(S)C_k(S) is a median graph. Every median graph is a partial cube; see Hammack et al. [8].

The mobile value for trees is part of the following characterization.

Theorem 5.7 [4]. Let GG be a connected graph with at least two vertices. Then Mob⁡μ(G)=2\operatorname{Mob}_{\mu}(G)=2 if and only if GG is a tree.

Theorem 5.5 provides a structural proof of the tree case, also stated in Dettlaff et al. [4].

Corollary 5.8 [4]. If TT is a tree with at least two vertices, then Mob⁡μ(T)=2\operatorname{Mob}_{\mu}(T)=2.

Proof. Section 2 gives Mob⁡μ(T)≥2\operatorname{Mob}_{\mu}(T)\ge2. Let S∈Mk(T)S\in\mathcal{M}_k(T) with k≥3k\ge3. By Theorem 5.5, all configurations in Ck(S)C_k(S) avoid the nonempty set BT(S)B_T(S). Thus the configurations in Ck(S)C_k(S) do not cover V(T)V(T). By Proposition 2.3, SS is not mobile.

The branch-barrier lemma also yields a lower bound on the number of connected components of a layer. Fix a branching vertex pp of TT, let r=deg⁡T(p)r=\deg_T(p), and order the components C1,…,CrC_1,\ldots,C_r of T−pT-p as in the definition of αp\alpha_p. For each i∈{1,…,r}i\in\{1,\ldots,r\}, put ℓi=∣L(T)∩V(Ci)∣\ell_i=|L(T)\cap V(C_i)|. For an integer k≥0k\ge0, let Qp(k)Q_p(k) be the set of integer vectors (a1,…,ar)(a_1,\ldots,a_r) with at least three positive coordinates satisfying 0≤ai≤ℓi0\le a_i\le\ell_i for every i∈{1,…,r}i\in\{1,\ldots,r\} and ∑i=1rai=k\sum_{i=1}^{r}a_i=k.

Lemma 5.9. Let TT be a tree and let pp be a branching vertex. If 3≤k<∣L(T)∣3\le k<|L(T)|, then RMk(T)\mathcal{R}^{k}_{\mathcal{M}}(T) has at least max⁡{2,∣Qp(k)∣}\max\{2,|Q_p(k)|\} connected components.

Proof. For each vector a=(a1,…,ar)∈Qp(k)a=(a_1,\ldots,a_r)\in Q_p(k), choose sets Si⊆L(T)∩V(Ci)S_i\subseteq L(T)\cap V(C_i) with ∣Si∣=ai|S_i|=a_i, and put Sa=⋃i=1rSiS_a=\bigcup_{i=1}^{r}S_i. Then SaS_a consists of kk leaves of TT, so it is a mutual-visibility set with αp(Sa)=a\alpha_p(S_a)=a. Lemma 5.3 places distinct vectors in distinct components, since each has at least three positive coordinates. This gives at least ∣Qp(k)∣|Q_p(k)| components.

For the bound of two, choose leaves in three distinct branches at pp and extend this selection to a set SS of kk leaves. This is possible since each branch contains a leaf and 3≤k<∣L(T)∣3\le k<|L(T)|. Choose z∈L(T)∖Sz\in L(T)\setminus S, and choose s∈Ss\in S in a branch other than the branch containing zz, and put S′=(S∖{s})∪{z}S'=(S\setminus\{s\})\cup\{z\}. Both sets are mutual-visibility sets of cardinality kk. Since s,zs,z lie in distinct branches, αp(S′)≠αp(S)\alpha_p(S')\ne\alpha_p(S). At least three branches are occupied by SS, so Lemma 5.3 places it and S′S' in distinct components. Together these bounds give at least max⁡{2,∣Qp(k)∣}\max\{2,|Q_p(k)|\} components.

Branching thus disconnects intermediate layers. We can now characterize the connected layers of a tree.

Theorem 5.10 (Connectivity of tree layers). Let TT be a tree with at least two vertices, and let 0≤k≤μ(T)0\le k\le\mu(T). Then RMk(T)\mathcal{R}^{k}_{\mathcal{M}}(T) is connected if and only if k∈{0,1,2,μ(T)}k\in\{0,1,2,\mu(T)\}.

Proof. If 3≤k<μ(T)=∣L(T)∣3\le k<\mu(T)=|L(T)|, then TT has at least four leaves and hence a branching vertex. Lemma 5.9 implies that RMk(T)\mathcal{R}^{k}_{\mathcal{M}}(T) is disconnected. This proves that the stated condition on kk is necessary.

Conversely, the layers of cardinality 0, 1, and 2 are connected, as noted in Section 2. It remains to consider k=μ(T)k=\mu(T). Let S∈Mk(T)S\in\mathcal{M}_k(T). By Lemma 5.1, S=L(HT(S))S=L(H_T(S)). We transform SS into L(T)L(T) by admissible slides. If S≠L(T)S \ne L(T), then ∣S∣=∣L(T)∣|S|=|L(T)| implies that some s∈Ss \in S is not a leaf of TT. Since ss is a leaf of HT(S)H_T(S), it has a neighbor x∈V(T)∖V(HT(S))x \in V(T) \setminus V(H_T(S)). Adjoining xx and the edge sxsx to HT(S)H_T(S) gives a subtree whose leaf set is S′=(S∖{s})∪{x}S'=(S\setminus\{s\})\cup\{x\}. This subtree is HT(S′)H_T(S'), since a tree is the minimal subtree containing all its leaves. By Lemma 5.1, S′S' is a mutual-visibility set, so sliding the token from ss to xx is admissible.

Each such move increases ∣V(HT(S))∣|V(H_T(S))| by one. Each move strictly increases ∣V(HT(S))∣|V(H_T(S))|, and such a move exists whenever S≠L(T)S \ne L(T). Since TT is finite, the procedure terminates at L(T)L(T). Every maximum configuration thus reaches L(T)L(T), proving connectivity.

The decomposition is especially explicit for spiders. A spider is a tree with exactly one branching vertex, denoted here by cc. Let r=deg⁡T(c)≥3r=\deg_T(c)\ge3. The components of T−cT-c are its legs, numbered 1,…,r1,\ldots,r. The ii-th leg is a path PℓiP_{\ell_i} on ℓi\ell_i vertices, not including cc.

Corollary 5.11 (Layers of a spider). Let TT be a spider whose r≥3r\ge3 legs have ℓ1,…,ℓr\ell_1,\ldots,\ell_r vertices, respectively. For every 3≤k≤r3\le k\le r,

RMk(T)≅⨆I⊆{1,…,r}∣I∣=k(□i∈IPℓi).\mathcal{R}_{\mathcal{M}}^k(T) \cong\mathop{\bigsqcup}_{\substack{I\subseteq\{1,\ldots,r\}\\ |I|=k}}\left(\mathop{\square}_{i\in I}P_{\ell_i}\right).

Consequently, RMk(T)\mathcal{R}_{\mathcal{M}}^k(T) has exactly (rk)\binom{r}{k} connected components. For each kk-element subset I⊆{1,…,r}I\subseteq\{1,\ldots,r\}, the corresponding component has order ∏i∈Iℓi\prod_{i\in I}\ell_i and diameter ∑i∈I(ℓi−1)\sum_{i\in I}(\ell_i-1).

Proof: By Lemma 5.1, every mutual-visibility set of cardinality at least three avoids the center cc and contains vertices in distinct legs. Conversely, choosing one vertex in each of any kk legs gives a mutual-visibility set. For such a configuration, the active branching set is {c}\{c\}, and the factors in Theorem 5.5 are precisely the chosen legs. Distinct choices of legs give distinct components, proving the formulas.

For cycles, all fixed-cardinality layers are connected. We prove this using a gap-balancing argument.

Cycles

Throughout this section, CnC_n denotes the cycle of order nn, with vertex set V(Cn)={v0,v1,…,vn−1}V(C_n)=\{v_0,v_1,\ldots,v_{n-1}\}, where the subscripts are taken modulo nn; we write Zn\mathbb{Z}_n for the cyclic group of integers modulo nn. We fix the orientation from viv_i to vi+1v_{i+1} to specify the order of the gap-vector entries. We use the following known value, which is the cycle case of Di Stefano [5].

Lemma 6.1 (Di Stefano [5]). For every n≥3n\ge3, the mutual-visibility number of the cycle CnC_n is μ(Cn)=3\mu(C_n)=3.

Since the layers of cardinality at most two are connected, it remains to study RM3(Cn)\mathcal{R}_{\mathcal{M}}^3(C_n).

Let S={x1,x2,x3}S=\{x_1,x_2,x_3\} be a set of three vertices of CnC_n, listed in cyclic order according to this orientation. These vertices divide CnC_n into three arcs whose interiors contain no vertex of SS. Let gig_i be the length of the arc from xix_i to xi+1x_{i+1} with interior disjoint from SS, taking subscripts modulo 33. We call γ(S)=(g1,g2,g3)\gamma(S)=(g_1,g_2,g_3) the gap vector of SS. Then g1,g2,g3g_1,g_2,g_3 are positive integers and g1+g2+g3=ng_1+g_2+g_3=n.

The next lemma characterizes visibility by gap vectors.

Lemma 6.2. Let n≥3n\ge3 and let SS be a set of three vertices of CnC_n with gap vector γ(S)=(g1,g2,g3)\gamma(S)=(g_1,g_2,g_3). Then SS is a mutual-visibility set if and only if gi≤⌊n/2⌋g_i\le\lfloor n/2\rfloor, for every i∈{1,2,3}i\in\{1,2,3\}.

Proof: For i∈{1,2,3}i \in\{1,2,3\}, let PiP_i be the arc of length gig_i joining xix_i and xi+1x_{i+1} whose interior contains no vertex of SS. The complementary arc has length n−gin-g_i and contains the remaining vertex of SS. Thus xi,xi+1x_i,x_{i+1} are mutually visible exactly when PiP_i is a geodesic. This occurs if and only if gi≤n−gig_i \le n-g_i or, equivalently, gi≤⌊n/2⌋g_i \le\lfloor n/2 \rfloor. Applying the same argument to the three pairs proves the characterization.

We describe the effect of token slides on gap vectors. Let S∈M3(Cn)S \in\mathcal{M}_3(C_n), with its gap vector ordered according to the fixed orientation. Reversing the orientation reorders entries but preserves visibility and TS adjacency. Suppose that the arcs corresponding to gig_i and gjg_j share an endpoint s∈Ss \in S, and let gℓg_\ell be the remaining gap. Sliding ss one edge into the gig_i-arc shortens it by one and lengthens the gjg_j-arc by one. Writing γ(S′)=(g1′,g2′,g3′)\gamma(S')=(g'_1,g'_2,g'_3) for the resulting configuration S′S', we have gi′=gi−1g'_i=g_i-1, gj′=gj+1g'_j=g_j+1, and gℓ′=gℓg'_\ell=g_\ell. The gaps still sum to nn. Figure 4 illustrates this operation for the transformation (3,4,5)↦(4,3,5)(3,4,5)\mapsto(4,3,5).

Gap-vector dynamics on $C_{12}$

Figure 4. Gap-vector dynamics on C12C_{12}. Let S={s1,s2,s3}S=\{s_1,s_2,s_3\}, with vertices listed in the fixed orientation and gap vector γ(S)=(3,4,5)\gamma(S)=(3,4,5). Sliding s2s_2 to the adjacent vertex s2′s'_2 gives S′=(S∖{s2})∪{s2′}S'=(S\setminus\{s_2\})\cup\{s'_2\} and γ(S′)=(4,3,5)\gamma(S')=(4,3,5), corresponding to (g1,g2,g3)↦(g1+1,g2−1,g3)(g_1,g_2,g_3)\mapsto(g_1+1,g_2-1,g_3).

Assume now that gi≥2g_i \ge2 and gj<⌊n/2⌋g_j < \lfloor n/2 \rfloor. The first inequality ensures an unoccupied destination and gi−1>0g_i-1>0. The second gives gj+1≤⌊n/2⌋g_j+1 \le\lfloor n/2 \rfloor. The unchanged third gap also remains positive and at most ⌊n/2⌋\lfloor n/2 \rfloor. Lemma 6.2 gives mutual visibility. Therefore, the corresponding token slide is admissible. We will use these admissible transfers between gaps in the proof below.

Theorem 6.3. For every n≥3n \ge3 and every 0≤k≤μ(Cn)0 \le k \le\mu(C_n), the layer RMk(Cn)\mathcal{R}^{k}_{\mathcal{M}}(C_n) is connected.

Proof: The layers of cardinality 00, 11, and 22 are connected. Since μ(Cn)=3\mu(C_n)=3, it remains to prove that RM3(Cn)\mathcal{R}^{3}_{\mathcal{M}}(C_n) is connected.

For n=3n=3, the layer RM3(C3)\mathcal{R}^{3}_{\mathcal{M}}(C_3) consists of a single vertex. If n=4n=4, then every triple in C4C_4 is mutually visible and determined by its unoccupied vertex. A token slide moves the unoccupied vertex to a neighbor. Consequently, RM3(C4)\mathcal{R}^{3}_{\mathcal{M}}(C_4) is isomorphic to C4C_4.

Assume now that n≥5n \ge5. Let S∈M3(Cn)S \in\mathcal{M}_3(C_n) and, after a cyclic relabeling if necessary, write γ(S)=(a,b,c)\gamma(S)=(a,b,c). Each gap is at most ⌊n/2⌋\lfloor n/2 \rfloor.

Suppose first that n=2t+1n=2t+1. The total capacity available in the two other gaps is (t−b)+(t−c)=a−1(t-b)+(t-c)=a-1. As long as a>1a>1, at least one of bb and cc is smaller than tt. Transfer one unit from the aa-gap to such a gap. This is an admissible token slide by the preceding observation. After a−1a-1 slides, the first gap is 11; the others are at most tt and sum 2t2t. Thus, the resulting gap vector is (1,t,t)(1,t,t). Suppose now that n=2tn = 2t. In this case, (t−b)+(t−c)=a(t-b) + (t-c) = a. While a>1a > 1, another gap is smaller than tt, allowing an admissible unit transfer to it. After a−1a-1 such transfers, the first gap has length 1. The other gaps sum to 2t−12t-1 and are at most tt. Consequently, their lengths are t−1t-1 and tt, in some order. The gap vector is thus (1,t−1,t)(1,t-1,t) or (1,t,t−1)(1,t,t-1), up to cyclic permutation.

We now connect all configurations with these gap vectors. First, let n=2t+1n = 2t+1 and, for r∈Znr \in\mathbb{Z}_n, set Ar={vr,vr+1,vr+t+1}A_r = \{v_r,v_{r+1},v_{r+t+1}\}. These are exactly the configurations with cyclic gap pattern (1,t,t)(1,t,t), up to cyclic permutation. In the sequences below, each arrow denotes an admissible TS move. For each rr, the sequence

Ar→{vr,vr+2,vr+t+1}→{vr,vr+2,vr+t+2}→Ar+1A_r \to\{v_r,v_{r+2},v_{r+t+1}\} \to\{v_r,v_{r+2},v_{r+t+2}\} \to A_{r+1}

consists of admissible token slides. Indeed, the two intermediate gap vectors are (2,t−1,t)(2,t-1,t) and (2,t,t−1)(2,t,t-1), respectively. Hence ArA_r and Ar+1A_{r+1} lie in the same component for every rr. Thus all ArA_r are mutually reachable.

Finally, let n=2tn = 2t, where t≥3t \ge3, and define Ar={vr,vr+1,vr+t}A_r = \{v_r,v_{r+1},v_{r+t}\} and Br={vr,vr+1,vr+t+1}B_r = \{v_r,v_{r+1},v_{r+t+1}\}. The gap vectors of ArA_r and BrB_r are (1,t−1,t)(1,t-1,t) and (1,t,t−1)(1,t,t-1), respectively. Sliding vr+tv_{r+t} to vr+t+1v_{r+t+1} gives the edge ArBrA_rB_r. Moreover, the sequence

Ar→{vr,vr+2,vr+t}→{vr,vr+2,vr+t+1}→Ar+1A_r \to\{v_r,v_{r+2},v_{r+t}\} \to\{v_r,v_{r+2},v_{r+t+1}\} \to A_{r+1}

also consists of admissible token slides. The intermediate gap vectors are (2,t−2,t)(2,t-2,t) and (2,t−1,t−1)(2,t-1,t-1). Thus all configurations ArA_r lie in one component; every BrB_r lies in that component because it is adjacent to ArA_r. The reduction above joins every vertex of RM3(Cn)\mathcal{R}^{3}_{M}(C_n) to some ArA_r when nn is odd, and to some ArA_r or BrB_r when nn is even. In each case, all configurations in these families are mutually reachable. Thus, RM3(Cn)\mathcal{R}^{3}_{M}(C_n) is connected.

This completes the connectivity proof for cycles, in contrast with the branch-occupancy obstructions found for trees.

Concluding remarks

The daisy-cube TAR skeleton ensures connectivity of RM(G)\mathcal{R}_{M}(G); TS edges may shorten its distances. We obtained metric bounds and proved that 3≤κ(RM(G))≤n3 \le\kappa(\mathcal{R}_{M}(G)) \le n for every connected graph GG of order n≥3n \ge3, with both bounds attained. Layer connectivity depends on the host. When m,n≥3m,n \ge3, every layer of Km,nK_{m,n} is connected except the maximum layer when m,n≥4m,n \ge4, which consists of mnmn isolated vertices. For trees, every component in a layer of cardinality at least three is a Cartesian product of subtrees determined by active branching vertices. For cycles, the gap-vector argument proves that every layer is connected.

A configuration is mobile if and only if the configurations in its layer component together cover V(G)V(G). Connectivity of a layer alone does not imply this covering property. For example, the maximum layer of K1,rK_{1,r}, with r≥3r \ge3, consists of the single configuration formed by all leaves. This layer is connected, but the center is never occupied along any legal move sequence, so the configuration is not mobile.

For trees, can Theorem 5.5 yield closed formulas for layer-component counts? For general hosts, open questions concern the complexity of fixed-layer reachability, graphs with every nonempty layer connected, components covering V(G)V(G), and whether κ(RM(G))=δ(RM(G))\kappa(\mathcal{R}_{M}(G)) = \delta(\mathcal{R}_{M}(G)).

AI Disclosure

We used ChatGPT and Codex (OpenAI) to improve readability and assist with LaTeX typesetting and figure preparation. No AI tools contributed to the mathematical content of the manuscript. The authors reviewed and edited all AI-assisted output and take full responsibility for the final manuscript.

References

  1. [1]B. Brešar and I. G. Yero. Lower (total) mutual-visibility number in graphs. Applied Mathematics and Computation, 465:128411, 2024. doi: 10.1016/j.amc.2023.128411. URL https://doi.org/10.1016/j.amc.2023.128411.
  2. [2]C. Bujtás, S. Klavžar, and J. Tian. Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets. Aequationes Mathematicae, 99:1883–1901, 2025. doi: 10.1007/s00010-025-01197-y. URL https://doi.org/10.1007/s00010-025-01197-y.
  3. [3]S. Cicerone, G. Di Stefano, L. Drożdek, J. Hedžet, S. Klavžar, and I. G. Yero. Variety of mutual-visibility problems in graphs. Theoretical Computer Science, 974:114096, 2023. doi: 10.1016/j.tcs.2023.114096. URL https://doi.org/10.1016/j.tcs.2023.114096.
  4. [4]M. Dettlaff, M. Lemańska, J. A. Rodríguez-Velázquez, and I. G. Yero. Mobile mutual-visibility sets in graphs. Ars Mathematica Contemporanea, 26(1):P1.10, 2026. doi: 10.26493/1855-3974.3410.9bc. URL https://doi.org/10.26493/1855-3974.3410.9bc.
  5. [5]G. Di Stefano. Mutual visibility in graphs. Applied Mathematics and Computation, 419:126850, 2022. doi: 10.1016/j.amc.2021.126850. URL https://doi.org/10.1016/j.amc.2021.126850.
  6. [6]R. Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, sixth edition, 2025. doi: 10.1007/978-3-662-70107-2. URL https://doi.org/10.1007/978-3-662-70107-2.
  7. [7]R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood. Token graphs. Graphs and Combinatorics, 28(3):365–380, 2012. doi: 10.1007/s00373-011-1055-9. URL https://doi.org/10.1007/s00373-011-1055-9.
  8. [8]R. Hammack, W. Imrich, and S. Klavžar. Handbook of Product Graphs. CRC Press, Boca Raton, second edition, 2011. ISBN 978-1-4398-1304-1. doi: 10.1201/b10959. URL https://doi.org/10.1201/b10959.
  9. [9]S. Klavžar and M. Mollard. Daisy cubes and distance cube polynomial. European Journal of Combinatorics, 80:214–223, 2019. doi: 10.1016/j.ejc.2018.02.019. URL https://doi.org/10.1016/j.ejc.2018.02.019.
  10. [10]D. Korže and A. Vesel. Mutual-visibility sets in Cartesian products of paths and cycles. Results in Mathematics, 79:116, 2024. doi: 10.1007/s00025-024-02139-x. URL https://doi.org/10.1007/s00025-024-02139-x.
  11. [11]M.-E. Messinger and L. Pipes. On pancyclicity in a mixed model for domination reconfiguration. Discrete Mathematics & Theoretical Computer Science, 28(2):21, 2026. doi: 10.46298/dmtcs.15637. URL https://doi.org/10.46298/dmtcs.15637.
  12. [12]N. Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. doi: 10.3390/a11040052. URL https://doi.org/10.3390/a11040052.
  13. [13]E. Shallcross, J. Tuite, A. Evans, A. Krishnakumar, and S. Boshar. Solution to some conjectures on mobile position problems, 2025. URL https://arxiv.org/abs/2507.16622v1.
  14. [14]Tonny K B and Shikhi M. Mutual-visibility of tree and its line graphs, 2026. URL https://arxiv.org/abs/2601.08270v2. Version 2, 19 May 2026.

Paper details

vlnc:W_rcdw4vus
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT, Codex

View statement
Looking for related papers…
Contents