Paper deep dive
Laplacian Spectral Shaping for Non-Uniform Scaling Formation Control of Open Multi-Agent Systems
Tao He, Gangshan Jing
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 7/21/2026, 2:33:50 AM
Summary
This paper proposes a distributed control framework for non-uniform scaling formation control in open multi-agent systems. It addresses the challenge of maintaining the 'formation spectrum' (positive semidefiniteness, correct kernel, and positive definiteness of the follower block) of a matrix-valued Laplacian under dynamic topology changes, including agent joining/leaving and edge addition/removal. The approach utilizes a 2-vertex-connected graph structure to allow any pair of agents to serve as leaders, supporting dynamic leader reassignment and avoiding predefined hierarchical structures.
Entities (7)
Relation Signals (6)
Open Multi-Agent Systems → experiences → Dynamic Topology Changes
confidence 95% · changes in number of agents, number of edges, and leader selection dynamically alter this Laplacian
Dynamic Topology Changes → destroys → Formation Spectrum
confidence 90% · destroying the required spectral properties: positive semidefiniteness, correct kernel, and positive definiteness of the follower block
Distributed Protocols → preserves → Formation Spectrum
confidence 90% · By implementing the protocols, the desired formation spectrum can be preserved under dynamic topology changes
Distributed Protocols → supports → Open Multi-Agent Systems
confidence 90% · In this paper, we develop distributed protocols to strategically adjust partial weights of the Laplacian matrix for formation control in arbitrary dimensional space... open multi-agent systems
Non-uniform Scaling Control → uses → Matrix-valued Laplacian
confidence 90% · The fundamental idea is encoding the desired formation shape as the kernel of a matrix-valued Laplacian.
2-vertex-connected Graph → enables → Leader Reassignment
confidence 85% · Moreover, our approach requires only that the nominal positions... 2-vertex-connected graphs allow any pair of agents to serve as leaders... enabling dynamic leader reconfiguration
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Non-uniform scaling control enables a multi-agent formation to adjust its shape by compressing or stretching independently along different coordinate axes through inter-agent interactions, offering high flexibility in complex environments. The fundamental idea is encoding the desired formation shape as the kernel of a matrix-valued Laplacian. In open multi-agent systems, however, changes in number of agents, number of edges, and leader selection dynamically alter this Laplacian, destroying the required spectral properties: positive semidefiniteness, correct kernel, and positive definiteness of the follower block (we summarize these properties as the formation spectrum). In this paper, we develop distributed protocols to strategically adjust partial weights of the Laplacian matrix for formation control in arbitrary dimensional space. By implementing the protocols, the desired formation spectrum can be preserved under dynamic topology changes including agent joining, edge addition, agent leaving, and edge removal, while any pair of agents can serve as leaders. Unlike existing Laplacian design methods for affine formation control under topology changes, the proposed approach requires a sparser sensing graph, avoids a predefined parent-child hierarchical structure, and supports leader reassignment. The effectiveness of the proposed protocols is validated through both theoretical analysis and numerical simulations.
Tags
Links
- Source: https://arxiv.org/abs/2607.16709v1
- Canonical: https://arxiv.org/abs/2607.16709v1
Trouble viewing inline? Open PDF directly →
Full Text
97,546 characters extracted from source content.
Expand or collapse full text
Laplacian Spectral Shaping for Non-Uniform Scaling Formation Control of Open Multi-Agent Systems Tao He 20231301010@stu.cqu.edu.cn Gangshan Jing jinggangshan@cqu.edu.cn School of Automation, Chongqing University, Chongqing, 400044, PRC Abstract Non-uniform scaling control enables a multi-agent formation to adjust its shape by compressing or stretching independently along different coordinate axes through inter-agent interactions, offering high flexibility in complex environments. The fundamental idea is encoding the desired formation shape as the kernel of a matrix-valued Laplacian. In open multi-agent systems, however, changes in number of agents, number of edges, and leader selection dynamically alter this Laplacian, destroying the required spectral properties—positive semidefiniteness, correct kernel, and positive definiteness of the follower block (we summarize these properties as the formation spectrum). In this paper, we develop distributed protocols to strategically adjust partial weights of the Laplacian matrix for formation control in arbitrary dimensional space. By implementing the protocols, the desired formation spectrum can be preserved under dynamic topology changes including agent joining, edge addition, agent leaving, and edge removal, while any pair of agents can serve as leaders. Unlike existing Laplacian design methods for affine formation control under topology changes, the proposed approach requires a sparser sensing graph, avoids a predefined parent-child hierarchical structure, and supports leader reassignment. The effectiveness of the proposed protocols is validated through both theoretical analysis and numerical simulations. keywords: Multi-agent systems, formation control, spectral shaping, matrix-valued Laplacian. †thanks: A preliminary version of this work [16] has been accepted for presentation at the IFAC World Congress 2026, where only agent joining as a follower was addressed. In contrast, this work contributes a unified framework covering all four elementary topology changes—agent joining, edge addition, agent leaving, and edge removal—and supports leader reassignment. Corresponding author Gangshan Jing. , 1 Introduction Distributed formation maneuver control enables collective shape transformations using only inter-agent local sensing, and has underpinned a wide range of applications, including high-speed cooperative payload transport [31], navigation through densely cluttered spaces [42], and self-organizing heterogeneous robot teams for complex missions [44]. Critically, the realization of such distributed cooperative control inherently depends on the underlying sensing graph. In realistic deployments, however, both edges and nodes of the sensing graph may change dynamically [30]. On the edge side, obstacle avoidance continuously perturbs inter-agent geometry, and sensing links may be intermittently blocked by occlusions or limited range, forcing edge removal or reconfiguration. Meanwhile, strategically adding new edges can accelerate synchronization convergence [3] while simultaneously providing redundant information pathways to enhance robustness [32]. On the node side, agents may join to augment mission capability or leave due to failure or energy depletion, resulting in a fully dynamic vertex set [12, 18].These scenarios give rise to an open multi-agent system, where the graph is neither static nor confined to predefined switching patterns [25, 27], but may undergo arbitrary edge addition/removal and agent joining/leaving events (we refer to this as fully dynamic topology changes). Existing formation maneuver control methods can be divided into two paradigms, as systematically compared in Table 1. The first uses nonlinear constraints such as distances [37, 33], bearings [40, 20, 32, 39], or distance ratios/angles [19, 5, 2, 4]. Built on minimally rigid graphs via Henneberg constructions, these methods naturally support agent joining and leaving, but they do not handle edge addition or removal, and their nonlinear controllers complicate stability analysis. Table 1: Comparison of Formation Maneuver Control Methods in ℝdR^d Method Maneuverability (DoF) Grapha Position-based [27] None (0) Star Static Displacement-based [43, 3] Translation (d) Connected Fully dynamic Distance-based [37, 33] Rotation-Translation ((d2)+d d2+d) Laman Partially dynamic Bearing-based [40, 20, 32, 39] Uniform Scaling-Translation (d+1) Laman Partially dynamic Angle/Distance-ratio-based [19, 5, 2, 4] Uniform Scaling-Rotation-Translation ((d2)+d+1 d2+d+1) Laman Partially dynamic Complex-Laplacian-based [23, 13, 10] Uniform Scaling-Rotation-Translation (4 in ℝ2R^2) 2-rooted Static Affine Formation [24, 41, 21] Affine (d2+d)(d^2+d) (d+1)-lateration Partially dynamic Our Work Non-uniform Scaling-Translation (2d) 2-vertex-connected Fully dynamic a Fully dynamic: supports all four primitive topology changes—agent joining, agent leaving, edge addition, and edge removal. Partially dynamic: supports only a subset of the primitive topology changes. Static: no changes are supported. The linear Laplacian-based paradigm encodes the target formation in the Laplacian null space, yielding linear controllers and facilitating global convergence analysis. Within this paradigm, displacement-based methods [43, 3] require only a connected graph and allow independent edge-weight adjustments; consequently, they support fully dynamic topology changes, but achieve only translation (d degrees of freedom, DoF). Complex-Laplacian-based methods [23, 13, 10] provide the additional ability to uniformly scale the formation, thereby enhancing maneuverability. However, this isotropic scaling mechanism restricts their adaptability to anisotropic environments. Consequently, they may compromise safety or efficiency by reducing scale in directions where it is unnecessary. This motivates the need for non-uniform scaling (independent scaling along each axis), which is supported by both affine formation methods [24, 41, 21] and the matrix-valued constraint framework [15]. However, the former, which handles topology changes [21], relies on a predefined hierarchical (d+1)(d+1)-rooted graph structure, lacks mechanisms for edge addition, and offers no structural flexibility to handle leader faults. The latter achieves non-uniform scaling under merely 22-rooted graphs with two leaders, but lacks mechanisms for dynamic topology changes, requires solving a centralized high-dimensional inverse eigenvalue problem for global convergence, and fixes the leader set a priori. This paper addresses these limitations by developing a fully distributed framework for non-uniform scaling formation maneuver control that operates under arbitrary topology changes. The main contributions are summarized as follows. (i) We introduce a unified algebraic representation for the Laplacian dynamics of open multi-agent systems. Based on this formulation, we develop distributed update laws that ensure maintainance of the required spectral property of the Laplacian during topology changes, including agent joining, agent leaving, edge addition, and edge removal. (i) We adopt a 2-vertex-connected graph structure to enable non-uniform scaling formation maneuver control in arbitrary dimensional space. In contrast to existing formation control methods [23, 41, 13, 10, 21] that require a predetermined and immutable leader set, the proposed framework supports dynamic leader reassignment. Moreover, compared with existing affine formation frameworks under topology changes (e.g., [21]), the proposed approach requires a sparser sensing graph, eliminates the need for predefined parent–child hierarchical structure, and provides a characterization of minimal compensatory edge sets for restoring 22-vertex-connectivity. The remainder of this paper is organized as follows. Section 2 introduces mathematical background and fundamentals of formation control. Section 3 states the problem. Section 4 details the spectral property maintenance strategy under topology changes. Section 5 presents numerical results and Section 6 concludes the paper and discusses future work. 2 Preliminaries 2.1 Notation and Graph Theory Throughout this paper, ℝR denotes the field of real numbers. ℝdR^d signifies the d-dimensional Euclidean space. The identity matrix is In∈ℝn×nI_n ^n× n, the all-ones vector is 1n∈ℝn1_n ^n, the zero tensor (scalar/vector/matrix) with context-appropriate dimensions is 0, the Kronecker product is ⊗ , and the symbols ⪰ and ≻ denote positive semi-definiteness and positive definiteness for matrices, respectively. The Special Orthogonal group is SO(d)=R∈ℝd×d∣R⊤R=Id,det(R)=1SO(d)=\R ^d× d R R=I_d, (R)=1\. We model the interaction network of a multi-agent system in ℝdR^d as an undirected graph G=(V,E)G=(V,E). The vertex set V=1,…,nV=\1,…,n\ represents agents. The edge set E⊆u,v∣u,v∈V,u≠vE \\u,v\ u,v∈ V,u≠ v\ captures both sensing and communication links: an edge u,v∈E\u,v\∈ E indicates that agents u and v can sense or exchange information with each other. The neighborhood of agent i is defined as Ni=j∈V:i,j∈EN_i=\\,j∈ V:\i,j\∈ E\,\. A matrix L=[Lij]∈ℝdn×dnL=[L_ij] ^dn× dn is called a matrix-valued Laplacian associated with an undirected graph G with n agents in ℝdR^d if it satisfies ∑j=1nLij=0 _j=1^nL_ij=0 for all i=1,…,ni=1,…,n, where for i≠ji≠ j, each block Lij∈ℝd×dL_ij ^d× d (with entries possibly positive, negative, or zero) represents the matrix weight of pair i,j\i,j\ (nonzero if i,j∈E\i,j\∈ E, and zero otherwise), and satisfies Lij=Lji⊤L_ij=L_ji . For a graph G, let G−vG-v (resp. G−eG-e) be the subgraph of G obtained by deleting a vertex v and all its incident edges (resp. deleting an edge e). Definition 1 (2-vertex-connected [7]). A graph G=(V,E)G=(V,E) is 2-vertex-connected if G−xG-x is connected for all x∈Vx∈ V. Definition 2 (2-rooted [23]). A graph G=(V,E)G=(V,E) is called 2-rooted if there exist distinct vertices r1,r2∈Vr_1,r_2∈ V, called the roots, such that for every w∈V∖r1,r2w∈ V \r_1,r_2\ and every x∈V∖wx∈ V \w\, there exists a path from r1,r2\r_1,r_2\ to w in G−xG-x. Lemma 1. If G=(V,E)G=(V,E) is 2-rooted with roots r1,r2\r_1,r_2\, then G′=(V,E′)G =(V,E ) with E′=E∪r1,r2E =E∪\\r_1,r_2\\ is 2-vertex-connected. pf We prove this by two cases. Case 1: x∉r1,r2x∉\r_1,r_2\. Since edge r1,r2∈E′\r_1,r_2\∈ E , r1r_1 and r2r_2 remain connected in G′−xG -x. For any w∈V∖r1,r2,xw∈ V \r_1,r_2,x\, the 2-rooted property of G guarantees a path from r1,r2\r_1,r_2\ to w in G′−xG -x. Thus G′−xG -x is connected. Case 2: x=r1x=r_1 (symmetric for x=r2x=r_2). For any w∈V∖r1,r2w∈ V \r_1,r_2\, the 2-rooted property of G gives a path from r2r_2 to w in G−r1G-r_1. Hence G′−xG -x is connected. Lemma 2. If G=(V,E)G=(V,E) is 2-vertex-connected, then G is 2-rooted, and any pair of distinct vertices u,v⊆V\u,v\ V can serve as roots. pf Fix any pair u,v⊆V\u,v\ V. For any w∈V∖u,vw∈ V \u,v\ and any x∈V∖wx∈ V \w\, at least one of u,vu,v lies in G−xG-x; the connectivity of G−xG-x then yields a path from that root to w in G−xG-x. Thus G is 2-rooted with roots u,v\u,v\. 2.2 Formation and Desired Shape A configuration of the agents in V is denoted as (p,R)(p,R), where p=[p1⊤,…,pn⊤]⊤∈ℝdnp=[p_1 ,…,p_n ] ^dn is the stacked vector of agent positions, and R∈SO(d)R (d) defines the axes along which non-uniform scaling transformation is applied. Consequently, a formation in ℝdR^d is fully characterized by the tuple (G,p,R)(G,p,R). Let (p~,R)( p,R) be a nominal configuration, where p~=[p~1⊤,…,p~n⊤]⊤∈ℝdn p=[ p_1 ,…, p_n ] ^dn is the nominal position vector that defines the reference shape of the formation. The desired shape manifold under non-uniform scaling is Π(p~,R)≔p=(In⊗S(R))p~+1n⊗τ∣s,τ∈ℝd, ( p,R) \p= (I_n S(R) ) p+1_n τ s,τ ^d \, (1) where S(R)=Rdiag(s)R⊤S(R)=Rdiag(s)R , s∈ℝds ^d and τ∈ℝdτ ^d denote the scaling and translation maneuver parameters, respectively. This formulation generalizes uniform scaling by allowing independent compression or stretching along orthogonal directions defined by R∈SO(d)R (d). As illustrated in Fig. 1, in narrow passages, the formation can compress along the restricted direction while maintaining adequate spacing in others, avoiding the excessive proximity and inefficient maneuvers associated with uniform scaling approaches [23, 19, 32]. The following lemma characterizes the dimension of the desired shape manifold. Lemma 3 ([15]). For a nominal formation (G,p~,R)(G, p,R), dim(Π(p~,R))=2d ( ( p,R))=2d if and only if for each l=1,…,dl=1,…,d, the set p~i,Rli∈V\ p^l_i,R\_i∈ V is not a singleton, where p~i,Rl p^l_i,R denotes the l-th coordinate of R⊤p~iR p_i. Narrow PassageRestricted ZonexxyyOriginal(1) Scale x(2) Scale y(a) R=I2R=I_2y′y x′x Narrow PassageOriginal(3) Scale x′x (4) Scale y′y (b) R′=[cos45∘sin45∘−sin45∘cos45∘]R = bmatrix 45 & 45 \\ - 45 & 45 bmatrix Figure 1: Non-uniform scaling transformations of the formation for obstacle avoidance along the axes defined by R and R′R , respectively. 2.3 Agent Dynamics and Shape Stabilization Each agent i∈Vi∈ V is governed by single-integrator dynamics p˙i=ui, p_i=u_i, (2) where pi∈ℝdp_i ^d is its position and ui∈ℝdu_i ^d is the control input. Since only distributed control is considered, agent i has access to solely relative information with respect to its neighbors NiN_i: pj−pi,j∈Ni\p_j-p_i,j∈ N_i\. To drive the configuration p toward the desired manifold Π(p~,R) ( p,R), a commonly used distributed control law takes the form ui=−∑j∈NiLij(pj−pi),u_i=- _j∈ N_iL_ij(p_j-p_i), (3) where the matrix weights Lij∈ℝd×dL_ij ^d× d (to be designed) act on the relative positions. In stacked form, the closed-loop system becomes p˙=−Lp, p=-Lp, (4) where L is a matrix-valued Laplacian. If, in addition, ker(L)=Π(p~,R) (L)= ( p,R) and L⪰0L 0, then using the Lyapunov function V=12‖p‖2V= 12\|p\|^2, it can be proved that p converges to the desired manifold Π(p~,R) ( p,R) asymptotically. 2.4 Formation Maneuvering and Leader Reconfiguration To enable the formation to actively execute translations and non-uniform scalings of the nominal shape, we adopt a leader-follower strategy. Specifically, a small set of agents, designated as leaders, are directly controlled to realize the desired maneuver, while the remaining followers, through the distributed control law, automatically adjust their positions to maintain the formation. Unlike the shape stabilization problem discussed in the previous subsection, formation maneuvering imposes additional requirements on the matrix-valued Laplacian. Given a leader set Vl⊂V_l⊂ V with follower set Vf=V∖VlV_f=V V_l, we have p=[pl⊤,pf⊤]⊤p=[p_l ,p_f ] and L=[LllLlfLflLff]L=[ smallmatrixL_l&L_lf\\ L_fl&L_f smallmatrix], accordingly. If ker(L)=Π(p~,R) (L)= ( p,R), then Lp=0Lp=0 for any p∈Π(p~,R)p∈ ( p,R). If the block LffL_f is nonsingular, followers are uniquely determined by leaders: pf=−(Lff)−1Lflpl.p_f=-(L_f)^-1L_flp_l. (5) In contrast to [15] where the leader set is fixed a priori, we further require that the leaders can be dynamically selected from the agents to accommodate leader failures or task-driven reconfigurations. Therefore, we introduce the following notion. Definition 3 (Formation Spectrum). For a nominal formation (G,p~,R)(G, p,R) with n agents in ℝdR^d, the matrix-valued Laplacian L∈ℝdn×dnL ^dn× dn is said to have a formation spectrum if it satisfies the following three conditions: (i) L⪰0L 0; (i) ker(L)=Π(p~,R) (L)= ( p,R); (i) Q⊤LQ≻0,∀Q∈Q LQ 0,\ \ ∀ Q where =Q⊗Id∣Q∈0,1n×(n−2),Q⊤Q=In−2Q=\Q I_d Q∈\0,1\^n×(n-2),\ Q Q=I_n-2\ selects any two agents as leaders, and Q⊤LQ LQ is the corresponding follower block. The constraint Q⊤LQ≻0Q LQ 0 for ∀Q∈∀ Q ensures that Lff≻0L_f 0 always holds no matter which two agents are selected as leaders. Such setting benefits for enhancing the adaptability of the formation to complex environments where leaders may need to be rechosen [22]. By Lemma 3, the following assumption ensures that dim(Π(p~l,R))=2d ( ( p_l,R))=2d for any two leaders, thereby establishing a one-to-one correspondence between the leader state and the maneuver parameters s and τ. Assumption 1. For the nominal formation (G,p~,R)(G, p,R), the configuration (p~,R)( p,R) satisfies ∏l=1dp~ji,Rl≠0 _l=1^d p^l_ji,R≠ 0 for every pair of distinct agents j,ij,i, where p~ji,Rl p^l_ji,R denotes the l-th coordinate of R⊤(p~j−p~i)R ( p_j- p_i). Assumption 1 is readily satisfied. Given any set of distinct nominal positions p~i\ p_i\, there always exists a rotation matrix R∈SO(d)R (d) such that Assumption 1 holds. To see this, observe that for each pair of distinct indices j,i\j,i\ and each coordinate l∈1,…,dl∈\1,…,d\, the equation p~ji,Rl=0 p^l_ji,R=0 defines a proper algebraic subset of SO(d)SO(d) of codimension at least one. Taking the union over the finitely many such pairs and coordinates yields a closed set ℱ⊂SO(d)F (d) which is therefore a finite union of lower-dimensional algebraic sets. Hence its complement SO(d)∖ℱSO(d) is nonempty. Choosing any R from this complement guarantees that Assumption 1 holds. Remark 1. Compared to classical affine formation control [41], which requires at least d+1d+1 leaders in ℝdR^d, the proposed approach needs only two leaders regardless of the dimension d. Moreover, our approach requires only that the nominal positions p~i\ p_i\ be pairwise distinct, avoiding the generic position assumptions (e.g., no three collinear in 2-D, no four coplanar in 3-D) commonly assumed in distance-ratio-based [4], angle-based [2], affine [41], clique-based [14], and bearing-based [8] methods. The following lemma provides a necessary graph-theoretic condition for the formation spectrum. Lemma 4. If the nominal formation (G,p~,R)(G, p,R) satisfies Assumption 1 and has a Laplacian L with a formation spectrum, then G is 22-vertex-connected. pf Suppose G is not 22-vertex-connected. Then there exists a cut vertex x such that G−xG-x has at least two connected components. Denote the vertex sets of these components by V1,…,VkV_1,…,V_k with k≥2k≥ 2. We consider two cases. Case 1: There exists a component ViV_i with |Vi|≥2|V_i|≥ 2. Choose two distinct agents r1,r2∈Vir_1,r_2∈ V_i as leaders. Let U=⋃j≠iVjU= _j≠ iV_j and U¯=V∖(U∪x) U=V (U∪\x\). Reorder the vertices so that the Laplacian L has the block form L=[LU¯U¯LU¯x0LxU¯LxxLxU0LUxLUU].L= bmatrixL_ U U&L_ Ux&0\\ L_x U&L_x&L_xU\\ 0&L_Ux&L_U bmatrix. (6) Set pβ=(px⊤,pU⊤)⊤p_β=(p_x ,p_U ) . By Lemma 3 and Assumption 1, we have dim(Π(p~β,R))=2d ( ( p_β,R))=2d. For any pβ∈Π(p~β,R)p_β∈ ( p_β,R), the equation Lp=0Lp=0 restricted to U gives [LUx,LUU]pβ=0.[L_Ux,L_U]p_β=0. (7) Hence the rows of [LUxLUU][L_Ux\;L_U] are linearly dependent. These rows are part of the follower block LffL_f, so LffL_f is singular—a contradiction. Case 2: All components are singletons. Choose leaders as two leaves. For any other leaf y, Lyxpx+Lyypy=0L_yxp_x+L_yp_y=0 for all p∈Πp∈ . With p=n⊗τp=1_n τ we get Lyx+Lyy=0L_yx+L_y=0, so Lyx(px−py)=0L_yx(p_x-p_y)=0. By Assumption 1, px−pyp_x-p_y spans ℝdR^d. Hence Lyx=0L_yx=0 and Lyy=0L_y=0. Thus rows of LffL_f indexed by leaves are zero, making LffL_f singular—a contradiction. Therefore G is 22-vertex-connected. Remark 2. Lemma 4 shows that the formation spectrum necessarily requires the underlying graph to be 22-vertex-connected. This condition is stronger than the 22-rooted graphs used in prior works [23, 15], but is nonetheless practical: any 22-rooted graph becomes 22-vertex-connected by adding an edge between its two roots (Lemma 1); in practice, such an edge naturally exists because the two leaders typically need to communicate. Moreover, 22-vertex-connected graphs allow any pair of agents to serve as leaders (Lemma 2), enabling dynamic leader reconfiguration—capabilities essential for open multi-agent systems. 3 Problem Statement We consider an open multi-agent system in which agents and interaction links may dynamically appear or disappear. The interaction topology evolves through one of four elementary operations at each step: agent joining, agent leaving, edge addition, or edge removal. We index the system after each such elementary operation by t∈ℕt . At stage t, the system is characterized by a nominal formation Ft=(Gt,p~t,R)F^t=(G^t, p^t,R), where Gt=(Vt,Et)G^t=(V^t,E^t). Our goal is to construct, for each FtF^t, a matrix-valued Laplacian Lt∈ℝdnt×dntL^t ^dn^t× dn^t that has a formation spectrum. To avoid centralized recomputation after each topological change, we seek a recursive update mechanism: when an elementary operation transforms FtF^t into Ft+1=(Gt+1,p~t+1,R)F^t+1=(G^t+1, p^t+1,R) with Gt+1=(Vt+1,Et+1)G^t+1=(V^t+1,E^t+1), the Laplacian should be updated to Lt+1L^t+1 in a local manner with minimum structural perturbation. Any such update can be expressed in the general form Lt+1=ℰt(Lt+Δt)+Δ¯t,L^t+1=E^t (L^t+ ^t )+ ^t, (8) where ℰt:ℝdnt×dnt→ℝdnt+1×dnt+1E^t:R^dn^t× dn^t ^dn^t+1× dn^t+1 is the dimension-adjustment operator for agent joining/leaving, while Δt=[Δijt] ^t=[ ^t_ij] and Δ¯t=[Δ¯ijt] ^t=[ _ij^t] encode local edge weight modifications applied before and after ℰtE^t, respectively, where Δijt∈ℝd×d ^t_ij ^d× d denotes the (i,j)(i,j)-th block of Δt ^t (and similarly for Δ¯t ^t). Associated with each update, we define Eadd=i,j∉Et|Δijt≠0 or Δ¯ijt≠0E_add=\\i,j\∉ E^t\,|\, ^t_ij≠ 0 or ^t_ij≠ 0\ (9) as the set of edges added to the graph, and Emod=i,j∈Et|Δijt≠0 or Δ¯ijt≠0E_mod=\\i,j\∈ E^t\,|\, ^t_ij≠ 0 or ^t_ij≠ 0\ (10) as the set of existing edges whose weights are modified. The challenge is to design these local updates so that Lt+1L^t+1 inherits the desired spectral properties from LtL^t, yet any naive local modification to the graph may disrupt these global spectral properties of the Laplacian matrix, as illustrated in Fig. 2. This leads to the following problem. Figure 2: Effect of a simple edge removal on the formation spectrum of the matrix-valued Laplacian L. (a) ker(L) (L) has four basis vectors bib_i, all nonzero eigenvalues λi _i are positive. (b) After deleting edge v1,v2\v_1,v_2\ (its weight set to 0), ker(L) (L) reduces to two basis vectors only, a negative eigenvalue appears. This raises the question: how to preserve the formation spectrum under dynamic topology changes? Problem 1. Given a nominal formation FtF^t under Assumption 1 and its Laplacian LtL^t possessing a formation spectrum. For each elementary operation (i)-(iv), design Δt ^t and Δ¯t ^t in (8) such that the induced Ft+1F^t+1 has a Laplacian Lt+1L^t+1 that also possesses a formation spectrum, and among all such designs, |Emod||E_mod| is minimized subject to the constraint that |Eadd||E_add| is minimized. 1. Agent joining: Add a new agent v∉Vtv∉ V^t with prescribed nominal position p~v∈ℝd p_v ^d, yielding p~t+1=[(p~t)⊤,p~v⊤]⊤ p^t+1=[( p^t) , p_v ] , Vt+1=Vt∪vV^t+1=V^t∪\v\, and ℰt(ℳ)=[ℳ000]E^t(M)=[ smallmatrixM&0\\ 0&0 smallmatrix]. 2. Edge addition: Add a new edge j,k∉Et\j,k\∉ E^t, yielding p~t+1=p~t p^t+1= p^t, Vt+1=VtV^t+1=V^t, ℰt(ℳ)=ℳE^t(M)=M, and j,k∈Et+1\j,k\∈ E^t+1. 3. Agent leaving: Remove an agent u∈Vtu∈ V^t and all its incident edges, yielding p~t+1=p~t|Vt+1 p^t+1= p^t|_V^t+1 (subvector indexed by Vt+1=Vt∖uV^t+1=V^t \u\), ℰt(ℳ)=ℳVt+1,Vt+1E^t(M)=M_V^t+1,V^t+1 (the principal submatrix indexed by Vt+1V^t+1), and ∀i∈Vt,u,i∉Et+1∀ i∈ V^t,\;\u,i\∉ E^t+1. 4. Edge removal: Remove an existing edge j,k∈Et\j,k\∈ E^t, yielding p~t+1=p~t p^t+1= p^t, Vt+1=VtV^t+1=V^t, ℰt(ℳ)=ℳE^t(M)=M, and j,k∉Et+1\j,k\∉ E^t+1. We prioritize minimizing |Eadd||E_add| since edge additions correspond to structural expansions of the interaction network, potentially requiring new sensing or communication links and thus incurring higher implementation cost. In contrast, edge modifications operate on existing interactions by adjusting edge weights without changing the underlying topology. 4 Spectral Property Maintenance under Topology Changes To maintain the spectral properties under topology changes in a distributed manner, we first introduce a matrix-weighted linear constraint from [15]. For any agent k and any two of its neighbors i,j∈Nki,j∈ N_k, the constraint is given by Wjkpik+Wkipjk=0,W_jkp_ik+W_kip_jk=0, (11) where pik=pi−pkp_ik=p_i-p_k, pjk=pj−pkp_jk=p_j-p_k, Wjk=diag(p~jk,R)R⊤W_jk=diag ( p_jk,R )R , Wki=diag(p~ki,R)R⊤W_ki=diag ( p_ki,R )R , p~ki,R=R⊤p~ki p_ki,R=R p_ki, p~ki=p~k−p~i p_ki= p_k- p_i, p~jk,R=R⊤p~jk p_jk,R=R p_jk, p~jk=p~j−p~k p_jk= p_j- p_k. Lemma 5 ([15]). The constraint (11) is invariant under the non-uniform scaling and translation transformations defined in (1). That is, if (pi,pj,pk)(p_i,p_j,p_k) satisfies (11), then for any s,τ∈ℝds,τ ^d, the transformed triplet (S(R)pi+τ,S(R)pj+τ,S(R)pk+τ)(S(R)p_i+τ,\;S(R)p_j+τ,\;S(R)p_k+τ) also satisfies (11), where S(R)=Rdiag(s)R⊤S(R)=Rdiag(s)R as in (1). Lemma 5 implies that if we construct a Laplacian matrix L based on (11), it always holds that Π(p~,R)⊆ker(L) ( p,R) (L), which lays the foundation for establishing a formation spectrum. We now solve the four primitive topology operations in Problem 1 under this matrix-weighted linear constraint. For notational simplicity, we use F, L, F+F^+, L+L^+, ℰE, Δ , and Δ¯ to denote FtF^t, LtL^t, Ft+1F^t+1, Lt+1L^t+1, ℰtE^t, Δt ^t, and Δ¯t ^t, respectively. 4.1 Agent Joining We now address agent joining in Problem 1. Let v∉Vv∉ V be the new agent with a pre-assigned nominal position p~v p_v. To integrate v into the formation while preserving the spectral properties, we connect it to two existing neighboring agents i,j∈Vi,j∈ V such that i,j∈E\i,j\∈ E, and set Eadd=i,v,j,vE_add=\\i,v\,\j,v\\. We next detail the construction of the Laplacian matrix for the updated formation. For the nominal formation (G,p~,R)(G, p,R), we first reorder the agents in V to place i and j at the end. The corresponding Laplacian matrix L can be partitioned as L=[LrrLrsLsrLss],L= bmatrixL_r&L_rs\\ L_sr&L_s bmatrix, (12) where subscript r corresponds to agents in V∖i,jV \i,j\ and s corresponds to agents in i,j\i,j\. For the triplet (i,j,v)(i,j,v), the constraint derived from (11) takes the matrix form Mijvpijv=0,M_ijvp_ijv=0, (13) where Mijv=[Wjv,Wvi,Wij]M_ijv= bmatrixW_jv,&W_vi,&W_ij bmatrix, Wij=diag(p~ij,R)R⊤W_ij=diag ( p_ij,R )R , pijv=[pi⊤,pj⊤,pv⊤]⊤p_ijv=[p_i ,p_j ,p_v ] . To embed this constraint distributively into the Laplacian framework, we define the positive semidefinite block Lijv=Mijv⊤DMijv∈ℝ3d×3d,L^ijv=M_ijv DM_ijv ^3d× 3d, (14) where D≻0D 0 is a diagonal design matrix that provides a degree of freedom for weighting the constraint. Following the update formula (8), we set Δ=0 =0 and use ℰE as defined in Problem 1 for agent joining. The matrix Δ¯ is obtained by embedding LijvL^ijv into a d|V+|×d|V+|d|V^+|× d|V^+| zero matrix according to the ordering (r,i,j,v)(r,i,j,v): Δ¯=Lpadijv(D)=[00000Wjv⊤DWjvWjv⊤DWviWjv⊤DWij0Wvi⊤DWjvWvi⊤DWviWvi⊤DWij0Wij⊤DWjvWij⊤DWviWij⊤DWij]. =L^ijv_pad(D)= bmatrix0&0&0&0\\ 0&W_jv DW_jv&W_jv DW_vi&W_jv DW_ij\\ 0&W_vi DW_jv&W_vi DW_vi&W_vi DW_ij\\ 0&W_ij DW_jv&W_ij DW_vi&W_ij DW_ij bmatrix. (15) The Laplacian for the extended formation (G+,p~+,R)(G^+, p^+,R) is L+=ℰ(L)+Lpadijv(D).L^+=E(L)+L^ijv_pad(D). (16) Theorem 1. Let F=(G,p~,R)F=(G, p,R) satisfy Assumption 1 and L be its Laplacian with a formation spectrum. For a new agent v with nominal position p~v p_v such that the extended nominal configuration (p~+=[p~⊤,p~v⊤]⊤,R)( p^+=[ p , p_v ] ,R) satisfies Assumption 1, choose two distinct agents i,j∈Vi,j∈ V with i,j∈E\i,j\∈ E. Then there exists a diagonal matrix D≻0D 0 such that setting Δ=0 =0, Δ¯ given by (15) yields a formation F+=(G+,p~+,R)F^+=(G^+, p^+,R) whose Laplacian L+L^+ given by (16) has a formation spectrum. Moreover, |Eadd|=2|E_add|=2 and |Emod|=1|E_mod|=1 are minimal. pf See Appendix A. Based on this construction, a fully distributed implementation is given in Algorithm 1. Algorithm 1 Distributed Laplacian Update for Agent Joining 0: Nominal formation (G,p~,R)(G, p,R) with Laplacian L; New agent v with p~v p_v; each agent i knows p~i p_i, NiN_i, Lij|j∈Ni\L_ij\,|\,j∈ N_i\ and can communicate with its neighbors 1: Agent v discovers candidates in sensing range and broadcasts a join request 2: Candidates respond with their nominal configurations and neighbor information; v selects two distinct agents i,ji,j from the candidates such that i,j∈E\i,j\∈ E 3: Agent v connects to i and j, sets Ni+←Ni∪vN_i^+← N_i∪\v\, Nj+←Nj∪vN_j^+← N_j∪\v\, Nv+←i,jN_v^+←\i,j\, computes Δij,Δiv,Δjv _ij, _iv, _jv per (15), and sends Δij _ij to i,ji,j, Δiv _iv to i, Δjv _jv to j 4: Set Lkl+←(ℰ(L))kl+ΔklL^+_kl←(E(L))_kl+ _kl for l∈Nk+l∈ N_k^+, k∈i,j,vk∈\i,j,v\. Remark 3. Theorem 1 enables iterative network expansion while preserving Laplacian spectral properties. Unlike centralized optimization approaches [26, 35], Algorithm 1 is fully distributed: it requires no global knowledge of the graph topology, agent indexing, or leader/follower roles; each new agent connects to only two existing agents in ℝdR^d via the local matrix-weighted constraint (13), with the corresponding Laplacian update (15) computed using only relative positions. In contrast, the methods in [36, 21] require each new agent to connect to d+1d+1 existing agents with scalar weights and are limited to ℝ2R^2 and ℝ3R^3. Moreover, unlike [21] where newly added agents are restricted to be followers, our construction allows the new agent v to be designated either as a follower or as a leader, enabling dynamic leader reallocation—a crucial feature for open multi-agent systems. 4.2 Edge Addition We now address Problem 1 for edge addition. At first glance, the task appears trivial: simply add a new edge e=j,k∉Ee=\j,k\∉ E with an arbitrary positive definite matrix weight. However, such naive addition would destroy the delicate kernel structure ker(L)=Π (L)= . To characterize admissible perturbations Δ=L+−L =L^+-L (with Δ¯=0 =0), define the graph GΔ=(V,EΔ)G_ =(V,E_ ) where EΔ=p,q∣Δpq≠0E_ = \\p,q\ _pq≠ 0 \. Then GΔG_ must satisfy the following necessary condition. Lemma 6. Let L∈ℝdn×dnL ^dn× dn be a matrix-valued Laplacian with ker(L)=Π (L)= and let Δ be a symmetric matrix such that L+=L+ΔL^+=L+ also satisfies ker(L+)=Π (L^+)= . Then in GΔG_ , the degree of every non‑isolated vertex is at least 22. pf Since ker(L)=ker(L+)=Π (L)= (L^+)= , for any p∈Πp∈ we have Lp=0Lp=0 and L+p=0L^+p=0, hence Δp=0 p=0. Thus Π⊆ker(Δ) ( ). Choosing p=n⊗τp=1_n τ gives (∑u∈VΔju)τ=0 ( _u∈ V _ju )τ=0 for all τ, so ∑u∈VΔju=0 _u∈ V _ju=0 for each vertex j. Suppose there exists a vertex j that has exactly one neighbor k in the graph induced by the nonzero blocks of Δ , i.e., Δjk≠0 _jk≠ 0 and Δjw=0 _jw=0 for all w≠j,kw≠ j,k. From the row‑sum condition, Δjj+Δjk=0 _j+ _jk=0. For any p∈Πp∈ , the j-th block of Δp=0 p=0 reads Δjjpj+Δjkpk=Δjj(pj−pk)=0. _jp_j+ _jkp_k= _j(p_j-p_k)=0. (17) Since this must hold for all p∈Πp∈ and under Assumption 1, we conclude Δjj=Δjk=0 _j= _jk=0, a contradiction. Hence no vertex can have degree exactly 11. If a vertex has no neighbors, its entire row of Δ is zero, which is allowed. Therefore, every non‑isolated vertex has degree at least 22. By Lemma 6, any nontrivial perturbation must involve at least three vertices; the simplest such structure is a triangle, whose associated constraint is exactly (11). To add only the single edge e, we therefore construct a perturbation Δ that corresponds to the Laplacian of a cycle containing e, which can be built from triangle primitives. 4.2.1 Construct the perturbation as the Laplacian of a cycle via triangulation By 22-vertex-connectivity, there exists a path from j to k. Without loss of generality, let its vertex sequence be 1,2,…,q1,2,…,q with 1=j1=j and q=kq=k. Adding e=j,ke=\j,k\ creates the cycle C=(1,2,…,q,1)C=(1,2,…,q,1). To construct a Δ that adds exactly e, we adopt a star-shaped triangulation of C with 11 (i.e., j) as the common vertex. Specifically, we add edges 1,i|i=3,…,q−1\\1,i\\,|\,i=3,…,q-1\, yielding triangles △1,2,3,△1,3,4,…,△1,q−1,q _1,2,3, _1,3,4,…, _1,q-1,q. For each triangle △1,i,i+1 _1,i,i+1 (i=2,…,q−1i=2,…,q-1), construct the 3d×3d3d× 3d local matrix L1i(i+1)(Di)L^1i(i+1)(D_i) as in (14) with the vertex order (1,i,i+1)(1,i,i+1). Then embed it into the dn×dndn× dn matrix Lpad1i(i+1)(Di)=0L^1i(i+1)_pad(D_i)=0. Specifically, let (a1,a2,a3)=(1,i,i+1)(a_1,a_2,a_3)=(1,i,i+1). For b,d∈1,2,3b,d∈\1,2,3\, (Lpad1i(i+1)(Di))abad=(L1i(i+1)(Di))bd. (L^1i(i+1)_pad(D_i) )_a_ba_d= (L^1i(i+1)(D_i) )_bd. (18) The total perturbation is Δ=∑i=2q−1Lpad1i(i+1)(Di). = _i=2^q-1L^1i(i+1)_pad(D_i). (19) We now cancel the contributions of the temporary diagonals. For each interior diagonal 1,i\1,i\ with i=3,…,q−1i=3,…,q-1, which is shared by triangles △1,i−1,i _1,i-1,i and △1,i,i+1 _1,i,i+1, cancellation of its contributions requires Wi,i−1⊤Di−1Wi−1,1+Wi,i+1⊤DiWi+1,1=0.W_i,i-1 D_i-1W_i-1,1+W_i,i+1 D_iW_i+1,1=0. (20) Substituting Wab=diag(p~ab,R)R⊤W_ab=diag( p_ab,R)R into (20) and simplifying with R⊤R=IR R=I gives a diagonal condition. For each coordinate l=1,…,dl=1,…,d, let dild_i^l denote the l-th diagonal entry of DiD_i, we obtain the scalar recurrence dil=γi−1ldi−1l,γi−1l=p~i−1,i,Rlp~i−1,1,Rlp~i,i+1,Rlp~i+1,1,Rl,i=3,…,q−1.d_i^l= _i-1^l\,d_i-1^l,\, _i-1^l= p_i-1,i,R^l p_i-1,1,R^l p_i,i+1,R^l p_i+1,1,R^l,\,i=3,…,q-1. (21) Under Assumption 1, p~ab,Rl≠0 p_ab,R^l≠ 0 for all distinct a,b∈Va,b∈ V and all l=1,…,dl=1,…,d, so the geometric factors γil _i^l are well-defined and non-zero. These factors completely determine the feasibility of the construction. Once D2≻0D_2 0 is chosen, all subsequent DiD_i are uniquely determined by the recurrence (21), and the necessary and sufficient condition for Di≻0D_i 0 is γil>0 _i^l>0 for all i,li,l. This leads to the following characterization. Theorem 2. Let F=(G,p~,R)F=(G, p,R) satisfy Assumption 1 and L be its Laplacian with a formation spectrum. For a new edge e=j,k∉Ee=\j,k\∉ E, suppose that there exists a path with vertex sequence j=1,2,…,q=kj=1,2,…,q=k such that all geometric factors γil _i^l defined in (21) are positive. Then, by constructing Δ via (19) with DiD_i specified in (21) where D2D_2 is designed to be positive definite, there exists ε>0 >0 such that the perturbed Laplacian L+=L+εΔL^+=L+ has a formation spectrum and Eadd=eE_add=\e\ is minimal. pf By 22-vertex-connectivity, the path with vertex sequence j=1,2,…,q=kj=1,2,…,q=k exists. Triangulating the cycle C=(1,2,…,q,1)C=(1,2,…,q,1) yields a set of triangles. Each edge of the cycle receives a nonzero matrix weight contribution from a single triangle, while each diagonal receives contributions from two triangles and is canceled by condition (20). Consequently, the nonzero off-diagonal blocks Δij _ij of Δ are precisely the edge weights of the cycle C. By further scaling all DiD_i with a sufficiently small common factor ε>0 >0, we ensure that the contributions to the original edges remain small enough to keep them nonzero, while the new edge e receives a nonzero contribution; hence only the edge e is added to G. Since all geometric factors defined in (21) are positive, then Δ⪰0 0; moreover, any principal submatrix Δff _f is also positive semidefinite. Since Lff≻0L_f 0 and Δff⪰0 _f 0, we obtain Lff+=Lff+εΔff≻0L^+_f=L_f+ _f 0. The remainder of the proof that L+L^+ has a formation spectrum follows the same structure as Theorem 1. 4.2.2 Construction feasibility independent of triangulation One might worry that the above analysis depends on the particular triangulation chosen. Since the number of triangulations of a cycle with q vertices is the (q−2)(q-2)-th Catalan number [6], which grows exponentially with q, searching over all possible triangulations for one admitting positive definite design matrices is computationally prohibitive. The following result shows that such a search is unnecessary: the feasibility condition is intrinsic to the cycle itself and independent of how it is triangulated. Theorem 3. Let C=(1,2,…,q,1)C=(1,2,…,q,1) be a cycle with nominal configuration (p~,R)( p,R) satisfying Assumption 1. Then either every triangulation of C admits positive definite diagonal matrices Dii=2q−1\D_i\_i=2^q-1 (as used in the construction Δ defined in (19)) satisfying (20), or none does. In other words, the existence of such matrices is independent of the chosen triangulation. pf Any two triangulations are connected by a finite sequence of edge flips [6]. It suffices to show that a single flip preserves existence. Consider a quadrilateral with vertices a,b,c,da,b,c,d in cyclic order. Two triangulations are possible: T1T_1 with diagonal (a,c)(a,c) (triangles △abc _abc and △acd _acd) and T2T_2 with diagonal (b,d)(b,d) (triangles △bcd _bcd and △bda _bda). Note that the local matrix Lxyz=Mxyz⊤DxyzMxyzL^xyz=M_xyz D_xyzM_xyz for a triangle is invariant under vertex permutation. Write dabcld_abc^l, dacdld_acd^l, dbcdld_bcd^l, dbdald_bda^l for the l-th diagonal entries of the design matrices D associated with each triangle. Then (20) yields: dacdl=γacldabcl,dbdal=γbdldbcdl,d_acd^l= _ac^ld_abc^l, d_bda^l= _bd^ld_bcd^l, (22) where γacl=p~bc,Rlp~ba,Rlp~cd,Rlp~da,Rl,γbdl=p~cd,Rlp~bc,Rlp~da,Rlp~ba,Rl. _ac^l= p_bc,R^l p_ba,R^l p_cd,R^l p_da,R^l, _bd^l= p_cd,R^l p_bc,R^l p_da,R^l p_ba,R^l. (23) Assumption 1 guarantees that the geometric factors γacl _ac^l and γbdl _bd^l are well-defined and non-zero. A direct computation shows γaclγbdl=(p~bc,Rl/p~da,Rl)2>0 _ac^l _bd^l=( p_bc,R^l/ p_da,R^l)^2>0 and γacl/γbdl>0 _ac^l/ _bd^l>0, so γacl _ac^l and γbdl _bd^l have the same sign. If T1T_1 admits positive definite solutions, then dabcl>0d_abc^l>0, dacdl>0d_acd^l>0, and γacl>0 _ac^l>0. Hence γbdl>0 _bd^l>0. Choosing any dbcdl>0d_bcd^l>0 and setting dbdal=γbdldbcdld_bda^l= _bd^ld_bcd^l yields positive entries, giving positive definite solutions for T2T_2. The converse follows by symmetry. Algorithm 2 Distributed Edge Addition Protocol 0: (G,p~,R)(G, p,R), L; agents j,kj,k with edge j,k\j,k\ to be added. 1: Path discovery: Agent k establishes communication with j, exchange their nominal positions p~j p_j, p~k p_k, and update their neighbor sets: Nj=Nj∪kN_j=N_j∪\k\, Nk=Nk∪jN_k=N_k∪\j\. 2: Agent k initiates a probe packet containing ℙ=[j,k]P=[j,k], ℙ~=[p~j,p~k] P=[ p_j, p_k], Γ=[] =[~] and sends it to all neighbors v∈Nk∖jv∈ N_k \j\. 3: while probe not reached j do 4: At current agent v with packet (ℙ=[j,…,f]P=[j,…,f], ℙ~=[p~j,…,p~f] P=[ p_j,…, p_f], Γ ): 5: for each w∈Nvw∈ N_v do 6: if w=jw=j then 7: Forward probe directly to j with packet [ℙ,v][P,v], [ℙ~,p~v][ P, p_v], and Γ . 8: else if w∉ℙw then 9: For each coordinate l=1,…,dl=1,…,d, compute the geometric factor γl=p~f,v,Rlp~f,j,Rlp~v,w,Rlp~w,j,Rl.γ^l= p_f,v,R^l p_f,j,R^l p_v,w,R^l p_w,j,R^l. 10: if γl>0γ^l>0 for all l then 11: Forward probe to w with updated packet [ℙ,v][P,v], [ℙ~,p~v][ P, p_v], and [Γ,γ][ ,γ]. 12: end if 13: end if 14: end for 15: end while 16: Δ computed by j: The probe reaches j carrying the complete cycle information in ℙP. Using ℙ~ P and Γ , j computes Δ via (19), where DiD_i, i∈2,…,q−1i∈\2,...,q-1\ are constructed from arbitrary D2≻0D_2 0 and Γ via (21). If multiple feasible paths exist, just use the first one. 17: Edge weight distribution: j sends an update packet along ℙP containing the computed edge weights for all edges in the cycle C. Each involved agent updates its local copy of the weights for its incident edges in C. 4.2.3 Finding a feasible cycle Theorem 3 liberates us from the exponential tyranny of triangulation choices. Yet a new challenge emerges: in large-scale networks, the edge e may belong to exponentially many cycles, each corresponding to a distinct path from j to k. Different cycles yield different geometric factors, and only those with all γil>0 _i^l>0 are feasible. Thus, even after eliminating the search over triangulations, we still face an exponential search over paths—a problem that seems equally intractable. Crucially, while any triangulation suffices for the final construction, only those with a local structure can guide the search itself. The star-shaped triangulation with a common vertex possesses exactly this property: each geometric factor γil _i^l depends only on four vertices—the current vertex, its predecessor, the candidate successor, and the common vertex (see (21)). This observation leads to a dynamic pruning strategy, implemented in Algorithm 2: at each step, any extension that violates γil>0 _i^l>0 is discarded. Because the condition is local, pruning can be performed in a fully distributed manner. The pruning is both sound—any feasible path satisfies the condition at every step and therefore survives—and effective, eliminating large numbers of infeasible paths early. When the geometric factors are not all positive, the single-edge addition via cycle triangulation fails. In this case, one can add a complete triangle △j,k,v _j,k,v with a neighbor v of j or k; set Δ to the perturbation corresponding to △j,k,v _j,k,v. This adds two edges simultaneously and always preserves the spectral properties. Remark 4. Unlike [11], which only achieves regular polygon formations under cyclic sensing, our construction realizes both regular and non‑regular polygon formations in a unified way. The key is to build a Laplacian for a cycle via triangulation. This construction requires a cycle C whose geometric factors in (21) are all positive. Once such a cycle is found, any triangulation of C succeeds—a fact established by Theorem 3. The remaining combinatorial challenge of finding a feasible cycle reduces to a path search problem, which can be solved efficiently by our distributed algorithm via pruning the search space using local positivity checks enabled by the locality of the geometric factors. Moreover, unlike existing methods tailored to minimally rigid graphs [19, 4, 5, 29], our edge-addition strategy allows the formation to evolve seamlessly from any 22-vertex-connected graph up to the complete graph while preserving the required spectral properties. 4.3 Agent Leaving We now address the agent leaving operation in Problem 1. Consider vertex u to be removed from the 22-vertex-connected graph G, with |Nu|∈[2,|V|−1]|N_u|∈[2,|V|-1]. Order all the vertices as U=V∖(Nu∪u)U=V (N_u∪\u\), N=NuN=N_u, and u. In this ordering, the Laplacian L admits the structure L=[LUULUN0LNULNNLNu0LuNLuu],L= bmatrixL_U&L_UN&0\\ L_NU&L_N&L_Nu\\ 0&L_uN&L_u bmatrix, (24) where Luu≻0L_u 0. Since ker(L)=Π(p~,R) (L)= ( p,R), we have Π(p~,R)⊆ker(Lu) ( p,R) (L_u) with Lu=[0LuNLuu]∈ℝd×dnL_u= bmatrix0&L_uN&L_u bmatrix ^d× dn denoting the block row corresponding to u. A naive approach would simply delete u and all its incident edges from G and zero out the corresponding blocks in L. Such naive removal, however, may cause that the remaining graph loses 22-vertex-connectivity, and the resulting Laplacian loses the formation spectrum. To overcome this, we follow the update formula (8) and set Δ¯=0 =0, while Δ is chosen as Δ=−Lu⊤Luu−1Lu. =-L_u L_u^-1L_u. (25) The Laplacian of the updated formation (G+,p~+,R)(G^+, p^+,R) is L+=ℰ(L−Lu⊤Luu−1Lu).L^+=E (L-L_u L_u^-1L_u ). (26) Theorem 4. Let F=(G,p~,R)F=(G, p,R) satisfy Assumption 1 and L be a Laplacian with a formation spectrum. Removing agent u∈Vu∈ V and all edges incident to u using Δ¯=0 =0 and Δ as in (25) yields a formation F+=(G+,p~+,R)F^+=(G^+, p^+,R) whose Laplacian L+L^+ given by (26) has a formation spectrum. pf We first show L+⪰0L^+ 0. Write L in block form as L=(ABB⊤C),Lu=(B⊤C),L= pmatrixA&B\\ B &C pmatrix, L_u= pmatrixB &C pmatrix, (27) where C=LuuC=L_u is symmetric positive definite and A corresponds to the remaining agents. Then Lu⊤Luu−1Lu=(BC−1B⊤B⊤C),L_u L_u^-1L_u= pmatrixBC^-1B &B\\ B &C pmatrix, (28) so M=L−Lu⊤Luu−1Lu=(A−BC−1B⊤000).M=L-L_u L_u^-1L_u= pmatrixA-BC^-1B &0\\ 0&0 pmatrix. (29) Since L⪰0L 0 and C≻0C 0, the Schur complement S=A−BC−1B⊤⪰0S=A-BC^-1B 0. Hence L+=ℰ(M)=S⪰0L^+=E(M)=S 0. Moreover, by the Schur complement rank theorem, rank(S)=rank(L)−rank(C)=(n−1)d−2drank(S)=rank(L)-rank(C)=(n-1)d-2d. We next prove Q⊤L+Q≻0Q L^+Q 0 for all Q∈Q . For any Q∈Q selecting two leaders with indices ℒL, let ℱF include the follower indices. Partition A and B accordingly: A=(AℱℱAℱℒAℒℱAℒℒ),B=(BℱBℒ).A= pmatrixA_FF&A_FL\\ A_LF&A_LL pmatrix, B= pmatrixB_F\\ B_L pmatrix. (30) Then Q⊤L+Q=Aℱℱ−BℱC−1Bℱ⊤Q L^+Q=A_FF-B_FC^-1B_F . In the original formation, the follower block for leaders ℒL is Lff=(AℱℱBℱBℱ⊤C),L_f= pmatrixA_FF&B_F\\ B_F &C pmatrix, (31) where Lff≻0L_f 0 because L has a formation spectrum. The Schur complement of C in LffL_f is Aℱℱ−BℱC−1Bℱ⊤A_FF-B_FC^-1B_F , which is therefore positive definite. Thus Q⊤L+Q≻0Q L^+Q 0. We now show ker(L+)=Π(p~+,R) (L^+)= ( p^+,R). For any p∈Π(p~,R)p∈ ( p,R), Lup=0L_up=0 implies (L−Lu⊤Luu−1Lu)p=Lp=0(L-L_u L_u^-1L_u)p=Lp=0, so Π(p~,R)⊆ker(M) ( p,R) (M). Removing u gives Π(p~+,R)⊆ker(L+) ( p^+,R) (L^+). Since rank(L+)=(n−1)d−2drank(L^+)=(n-1)d-2d, we have dim(ker(L+))=2d=dim(Π(p~+,R)) ( (L^+))=2d= ( ( p^+,R)), hence ker(L+)=Π(p~+,R) (L^+)= ( p^+,R). Thus L+L^+ has a formation spectrum. By Lemma 4, G+G^+ is 22-vertex-connected. The number of added edges satisfies 0≤|Eadd|≤(|Nu|2)0≤|E_add|≤ |N_u|2, where the upper bound corresponds to forming a complete graph among the neighbors of the departing agent. The distributed Laplacian update protocol is similar to Algorithm 1, hence omitted. Remark 5. Compared with existing works on graph biconnectivity maintenance [9, 28, 1], which focus exclusively on topological connectivity, our algorithm preserves the critical spectral properties of the Laplacian while ensuring that the resulting graph remains 22‑vertex‑connected. Unlike the affine framework construction in [21], which requires a predefined parent–child hierarchical structure, our method operates purely on local neighborhood information. Moreover, our approach imposes no restriction on the number of neighbors of the departing agent. 4.4 Edge Removal We now address the edge removal operation in Problem 1. By lemma 4 and the fact that Laplacian L has a formation spectrum, G is 22-vertex-connected. Removing e=j,k∈Ee=\j,k\∈ E yields H=G−eH=G-e, which may not satisfy the 22-vertex-connectivity required for G+G^+. The following theorem characterizes the minimal number of compensatory edges required to restore 22-vertex-connectivity. Theorem 5. Let G=(V,E)G=(V,E) be a 22-vertex-connected graph with |V|≥4|V|≥ 4, e=j,k∈Ee=\j,k\∈ E, and H=G−eH=G-e with dH(v)d_H(v) denoting the degree of v in H. Then H is 22-vertex-connected if and only if there exist two cycles C1,C2C_1,C_2 in G such that e∈E(C1)∩E(C2)e∈ E(C_1)∩ E(C_2) and V(C1)∩V(C2)=j,kV(C_1)∩ V(C_2)=\j,k\. Otherwise, the minimum number of new edges (distinct from e) needed to restore 22-vertex-connectivity is 1 when maxdH(j),dH(k)≥2 \d_H(j),d_H(k)\≥ 2, and 2 when dH(j)=dH(k)=1d_H(j)=d_H(k)=1. pf We prove it by considering three cases. Case (i): H is 22-vertex-connected. (Necessity) If H is 22-vertex-connected, then by Menger’s theorem there exist two internally vertex-disjoint paths P1,P2P_1,P_2 with endpoints j and k. Adding the edge e to P1P_1 and P2P_2 yields two cycles C1C_1 and C2C_2, both containing e and satisfying V(C1)∩V(C2)=j,kV(C_1)∩ V(C_2)=\j,k\. (Sufficiency) Conversely, suppose there are two cycles C1,C2C_1,C_2 with e∈E(C1)∩E(C2)e∈ E(C_1)∩ E(C_2) and V(C1)∩V(C2)=j,kV(C_1)∩ V(C_2)=\j,k\. Let Pi=Ci−eP_i=C_i-e (i=1,2i=1,2); then P1,P2P_1,P_2 are internally vertex-disjoint paths. We prove that G−eG-e is 22-vertex-connected by showing that G−e−xG-e-x is connected for every x∈Vx∈ V. Subcase 1: x=jx=j (symmetric for x=kx=k). Then G−e−j=G−jG-e-j=G-j. Since G is 22-vertex-connected, G−e−jG-e-j is connected. Subcase 2: x∉j,kx∉\j,k\. The graph G−xG-x is connected because G is 22-vertex-connected. If G−x−eG-x-e is disconnected then G−xG-x contains no path between j and k other than the edge e. However, since x∉j,kx∉\j,k\ and P1,P2P_1,P_2 are internally vertex-disjoint, at most one of them contains x. Hence at least one of P1,P2P_1,P_2 remains a path between j and k in G−xG-x, a contradiction. Thus (G−e)−x(G-e)-x is connected. Case (i): H is not 22-vertex-connected and maxdH(j) \d_H(j) ,dH(k)≥2,d_H(k)\≥ 2. Without loss of generality, let dH(j)≥2d_H(j)≥ 2. We first show that there exists a vertex w∈Nj(H)∖Nk(H)w∈ N_j(H) N_k(H) which is not a cut vertex of H. Suppose, for contradiction, that no such w exists. Let u,v∈Nj(H)u,v∈ N_j(H) be distinct. The following statements hold. • If u,v∈Nk(H)u,v∈ N_k(H), then the cycles (j,u,k,j)(j,u,k,j) and (j,v,k,j)(j,v,k,j) satisfy the condition of Case (i), contradiction. • If u is a cut vertex but v∈Nk(H)v∈ N_k(H), then H−uH-u separates j and k (since H−u=G−u−eH-u=G-u-e is disconnected and G−uG-u is connected, H−uH-u has exactly two components separated by e). However, the path from j to v to k connects them in H−uH-u, a contradiction. The symmetric case is similar. • If both u and v are cut vertices of H, then H−uH-u and H−vH-v separates j and k (similar to the proof above). Because G is 22-vertex-connected, there is a path P from j to k in G avoiding e. Then P lies in H and must pass through both u and v (otherwise it contradicts that H−u,H−vH-u,H-v separate j,kj,k). Then P contains a subpath from v to k avoiding u, so in H−uH-u the edge j,v\j,v\ together with this subpath connects j to k, contradiction. Thus, such a w exists. Now add edge k,w\k,w\ to H, yielding H′H . We show H′H is 22-vertex-connected. Take any x∈Vx∈ V, • if x∈j,kx∈\j,k\, then H′−xH -x contains G−xG-x (connected); • if x∉j,kx∉\j,k\ and x is not a cut vertex of H, then H−xH-x connected implies H′−xH -x connected; • if x∉j,kx∉\j,k\ and x is a cut vertex of H, then H−xH-x separates j and k (similar to the proof above). Since w is a non‑cut vertex, w≠xw≠ x, and w∈Nj(H)w∈ N_j(H) lies in the component of j. The new edge f=k,wf=\k,w\ thus connects the two components, so H′−xH -x is connected. Case (i): H is not 22-vertex-connected and dH(j)=dH(k)=1d_H(j)=d_H(k)=1. Let v and w be the unique neighbours of j and k in H, respectively. We first show v≠wv≠ w. If v=wv=w, then G contains the triangle △j,k,v _j,k,v. Since |V|≥4|V|≥ 4, there exists a vertex x≠j,k,vx≠ j,k,v. Because G is 22-vertex-connected, G−vG-v is connected, so x must be adjacent to j or k in G. But then dH(j)≥2d_H(j)≥ 2 or dH(k)≥2d_H(k)≥ 2, contradicting dH(j)=dH(k)=1d_H(j)=d_H(k)=1. Thus v≠wv≠ w. Adding a single edge to H can eliminate at most one of the leaves j,kj,k, leaving the other leaf’s neighbor as a cut vertex. Hence adding edges f1=j,wf_1=\j,w\ and f2=k,vf_2=\k,v\ to H yields H′H , which is 22-vertex-connected; the verification is analogous to Case (i) and omitted. jjkkaabbccwwf (a) jjkkvvbbccwwf1f_1f2f_2 (b) jjkkaabbccdd (c) Figure 3: Three cases of restoring 22-vertex connectivity after removing edge j,k\j,k\ from G. (a) Adding one compensatory edge k,w\k,w\ suffices to restore 22-vertex connectivity. (b) Two compensatory edges j,w\j,w\ and k,v\k,v\ are required. (c) No compensatory edge is needed. For edge removal, we take ℰE as the identity and Δ¯=0 =0, so the update reduces to L+=L+ΔL^+=L+ . We now translate each case in Theorem 5 into a concrete construction of Δ⪰0 0, presenting them in the order (i), (i), (i) for conciseness. Case (i): H is not 22-vertex-connected and maxdH(j) \d_H(j) ,dH(k)≥2,d_H(k)\≥ 2. A single compensatory edge suffices to restore 22-vertex connectivity (see Fig. 3(a)). Without loss of generality, assume dH(j)≥2d_H(j)≥ 2 and let w∈Nj(H)∖Nk(H)w∈ N_j(H) N_k(H) be a non-cut vertex of H (its existence is guaranteed in the proof of Theorem 5 and such w can be determined locally via two-hop neighbor information of agent j [34]). For each candidate w, seek D≻0D 0 such that the perturbation Lpadjkw(D)L^jkw_pad(D) (for △j,k,w _j,k,w as in (18)) satisfies: Lkj+Wwj⊤DWkw=0,Ljw+Wkw⊤DWjk≠0.L_kj+W_wj DW_kw=0, L_jw+W_kw DW_jk≠ 0. (32) The first condition cancels edge j,k\j,k\, while the second preserves edge j,w\j,w\. If such D≻0D 0 exists, we set Δ=Lpadjkw(D), =L^jkw_pad(D), (33) completing the edge removal operation for this case. Here Eadd=k,wE_add=\\k,w\\ and |Eadd|=1|E_add|=1 is minimal by Theorem 5. The corresponding distributed Laplacian update protocol is similar to Algorithm 1, and is therefore omitted. Case (i): H is not 22-vertex-connected and dH(j)=dH(k)=1d_H(j)=d_H(k)=1. Let v and w be the unique neighbors of j and k in H, with v≠wv≠ w (see Fig. 3(b)). Find D1≻0D_1 0 and D2≻0D_2 0 such that the perturbations Lpadjkw(D1)L^jkw_pad(D_1) (for △j,k,w _j,k,w as in (18)) and Lpadjkv(D2)L^jkv_pad(D_2) (for △j,k,v _j,k,v as in (18)) satisfy: Ljk+Wkw⊤D1Wwj+Wkv⊤D2Wvj=0,Ljv+Wkv⊤D2Wjk≠0,Lkw+Wwj⊤D1Wjk≠0. split&L_jk+W_kw D_1W_wj+W_kv D_2W_vj=0,\\ &L_jv+W_kv D_2W_jk≠ 0, L_kw+W_wj D_1W_jk≠ 0. split (34) The first condition cancels edge j,k\j,k\, while the second and third preserve edges j,v\j,v\ and k,w\k,w\, respectively. If such D1,D2≻0D_1,D_2 0 exist, we set Δ=Lpadjkw(D1)+Lpadjkv(D2), =L^jkw_pad(D_1)+L^jkv_pad(D_2), (35) completing the edge removal operation for this case. Here Eadd=j,w,k,vE_add=\\j,w\,\k,v\\ and |Eadd|=2|E_add|=2 is minimal by Theorem 5. The corresponding distributed Laplacian update protocol is similar to Algorithm 1, and is therefore omitted. Case (i): H is 22-vertex-connected (see Fig. 3(c)). Since H is already 22-vertex-connected, no compensatory edges are needed. However, the Laplacian L still contains the contribution of edge j,k\j,k\, which must be algebraically eliminated. We achieve this by considering an inverse operation of the edge addition method presented in Section 4.2. Specifically, we construct a cycle-based perturbation matrix that exactly removes j,k\j,k\ without introducing any new edges. The key modifications to Algorithm 2 are as follows. At agent k, for each v∈Nk∖jv∈ N_k \j\, we seek a design matrix Dk≻0D_k 0 such that the perturbation Lpadjkv(Dk)L^jkv_pad(D_k) (constructed for triangle △j,k,v _j,k,v as in (18)) satisfies: Lkj+Wvj⊤DkWkv=0,Lkv+Wvj⊤DkWjk≠0.L_kj+W_vj D_kW_kv=0, L_kv+W_vj D_kW_jk≠ 0. (36) The first condition cancels edge j,k\j,k\, while the second preserves edge v,k\v,k\. The perturbation also introduces a nonzero contribution to edge j,v\j,v\, which will be canceled in a later step. If such Dk≻0D_k 0 exists, agent k sends a probe to v containing =[Dk]D=[D_k] and the information in Algorithm 2. At current agent v with packet (ℙ=[j,…,f]P=[j,…,f], ℙ~=[p~j,…,p~f] P=[ p_j,…, p_f], =[Dk,…,Df]D=[D_k,…,D_f], Γ ). For each w∈Nvw∈ N_v: • If w=jw=j, the probe is forwarded directly to j with the current packet after verifying that Ljv+Wfv⊤DfWjf≠0.L_jv+W_fv D_fW_jf≠ 0. (37) • Else if w∉ℙw , we seek a design matrix Dv≻0D_v 0 such that the perturbation Lpadjvw(Dv)L^jvw_pad(D_v) (constructed for triangle △j,v,w _j,v,w as in (18)) satisfies: Wvf⊤DfWfj+Wvw⊤DvWwj=0,Lvw+Wwj⊤DvWjv≠0. split&W_vf D_fW_fj+W_vw D_vW_wj=0,\\ &L_vw+W_wj D_vW_jv≠ 0. split (38) The first condition cancels the contribution to edge j,v\j,v\ introduced by the previous perturbation Lpadjfv(Df)L^jfv_pad(D_f), while the second preserves edge v,w\v,w\. The perturbation Lpadjvw(Dv)L^jvw_pad(D_v) also introduces a nonzero contribution to edge j,w\j,w\, which will be canceled in a later step. If such Dv≻0D_v 0 exists, agent v sends a probe to w containing [,Dv][D,D_v] and the information in Algorithm 2. When the probe reaches j, unlike in Algorithm 2, the perturbation Δ is constructed directly from these DiD_i using (19). Here Eadd=∅E_add= , and |Eadd|=0|E_add|=0 is minimal by Theorem 5. As a direct extension of Theorem 5, Theorem 2, and Theorem 1, the constructions for Cases (i)–(i) provide explicit updates Δ such that, under the stated conditions, L+L^+ has a formation spectrum and (G+,p~+,R)(G^+, p^+,R) satisfies Assumption 1. In each case, the added edge set EaddE_add (explicitly given above) is of minimal size as characterized by Theorem 5. Remark 6. From a graph-theoretic perspective, Theorem 5 addresses a specific augmentation problem: given a 22-vertex-connected graph G and an edge e to be removed, how to find a smallest set of new edges (distinct from e) that restores 22-vertex-connectivity to G−eG-e. This contrasts with classical graph augmentation problems [9, 28], which typically consider adding edges to an arbitrary graph to achieve biconnectivity without the constraint of excluding a specific edge. Our contribution extends beyond this combinatorial characterization: we translate each case into a constructive Laplacian update protocol that maintains the desired spectral properties required for formation control. 123[500−6][ smallmatrix5&0\\ 0&-6 smallmatrix][−3000−3][ smallmatrix-30&0\\ 0&-3 smallmatrix][−6002][ smallmatrix-6&0\\ 0&2 smallmatrix] (a) Initial △1,2,3 _1,2,3 1234[500−6][ smallmatrix5&0\\ 0&-6 smallmatrix][−3000−3][ smallmatrix-30&0\\ 0&-3 smallmatrix][−3000−6][ smallmatrix-30&0\\ 0&-6 smallmatrix][−7.5001.5][ smallmatrix-7.5&0\\ 0&1.5 smallmatrix] (b) Add vertex 4, remove 1,3\1,3\ 12345[500−6][ smallmatrix5&0\\ 0&-6 smallmatrix][−3000−3][ smallmatrix-30&0\\ 0&-3 smallmatrix][−3000−6][ smallmatrix-30&0\\ 0&-6 smallmatrix][−3000−6][ smallmatrix-30&0\\ 0&-6 smallmatrix][−10001.2][ smallmatrix-10&0\\ 0&1.2 smallmatrix] (c) Add vertex 5, remove 1,4\1,4\ 123456[500−6][ smallmatrix5&0\\ 0&-6 smallmatrix][−3000−3][ smallmatrix-30&0\\ 0&-3 smallmatrix][−3000−6][ smallmatrix-30&0\\ 0&-6 smallmatrix][−3000−6][ smallmatrix-30&0\\ 0&-6 smallmatrix][−1500−6][ smallmatrix-15&0\\ 0&-6 smallmatrix][−30001][ smallmatrix-30&0\\ 0&1 smallmatrix] (d) Add vertex 6, remove 1,5\1,5\ 1234567[500−6][ smallmatrix5&0\\ 0&-6 smallmatrix][−3000−3][ smallmatrix-30&0\\ 0&-3 smallmatrix][−3000−6][ smallmatrix-30&0\\ 0&-6 smallmatrix][−3000−6][ smallmatrix-30&0\\ 0&-6 smallmatrix][−1400−5.91][ smallmatrix-14&0\\ 0&-5.91 smallmatrix][−30001][ smallmatrix-30&0\\ 0&1 smallmatrix][−200−0.1][ smallmatrix-2&0\\ 0&-0.1 smallmatrix][−200−0.9][ smallmatrix-2&0\\ 0&-0.9 smallmatrix] (e) Add vertex 7 1234567[500−6][ smallmatrix5&0\\ 0&-6 smallmatrix][−3000−3][ smallmatrix-30&0\\ 0&-3 smallmatrix][−3000−6][ smallmatrix-30&0\\ 0&-6 smallmatrix][−3000−6][ smallmatrix-30&0\\ 0&-6 smallmatrix][−30001][ smallmatrix-30&0\\ 0&1 smallmatrix][−3000−6.67][ smallmatrix-30&0\\ 0&-6.67 smallmatrix][−3000−60][ smallmatrix-30&0\\ 0&-60 smallmatrix] (f) Remove 5,6\5,6\ Figure 4: Edge weight evolution through agent joining and edge removal. Solid black edges: existing edges; dashed red edges: edges to be removed; red edges: newly added edges. 5 Simulation This section presents numerical simulations to validate the theoretical results. Four experiments are conducted. The first constructs a matrix-valued Laplacian for a cycle graph, illustrating the iterative update mechanism described in (8). The other three couple the spectral property maintenance framework with the formation tracking control law from [16], demonstrating formation maneuvers under dynamic topology changes, e.g., agent joining, agent leaving, and edge removal. (Experiments on edge addition and leader reassignment are omitted for brevity, as they follow the same pattern.) For completeness, the control law is described as follows. Each leader i∈Vli∈ V_l tracks a predefined trajectory via ui=−α1tanh(α2(pi−pi∗))+p˙i∗,u_i=- _1 ( _2(p_i-p^*_i))+ p^*_i, (39) where pi∗=S(R)p~i+τp^*_i=S(R) p_i+τ, α1,α2>0 _1, _2>0 are control gains, and tanh(⋅) (·) denotes the hyperbolic tangent function. Each follower i∈Vfi∈ V_f maintains the formation using relative position measurements via ui=−β1∑j∈NiLij(pj−pi)−β2sgn(∑j∈NiLij(pj−pi)),u_i=- _1 _j∈ N_iL_ij(p_j-p_i)- _2sgn\! ( _j∈ N_iL_ij(p_j-p_i) ), (40) where β1,β2>0 _1, _2>0 are control gains, sgn(⋅)sgn(·) denotes the signum function, and LijL_ij are the matrix-valued edge weights designed in previous sections. Agents 1 and 2 are designated as leaders, and the others are followers in all simulations. 5.1 Laplacian Construction for a Cycle Graph This subsection constructs a matrix-valued Laplacian for a cycle graph using the iterative update mechanism (8). The resulting Laplacian will be used as the initial Laplacian in the subsequent formation maneuver control experiments. We construct a cycle formation in ℝ2R^2 with R=I2R=I_2, starting from the triangle △1,2,3 _1,2,3 with nominal positions p~1=[−3,3]⊤ p_1=[-3,3] , p~2=[3,2]⊤ p_2=[3,2] , p~3=[2,0]⊤ p_3=[2,0] . For the initial triplet (i,j,v)=(1,2,3)(i,j,v)=(1,2,3), we form the constraint matrix M123M_123 as in (13) and set D=I2D=I_2 in (14). The resulting Laplacian L123=M123⊤DM123L^123=M_123 DM_123 yields the edge weight matrices (the off-diagonal blocks of L123L^123) displayed on each edge in Fig. 4(a). To add vertex 44 with p~4=[1,−1]⊤ p_4=[1,-1] while removing edge 1,3\1,3\, we combine the agent joining and edge removal operations. Following (16), we first pad L123L^123 to accommodate vertex 44: ℰ(L123)=[L123000]E(L^123)=[ smallmatrixL^123&0\\ 0&0 smallmatrix]. For the triplet (i,j,v)=(1,3,4)(i,j,v)=(1,3,4), we construct L134(D)L^134(D) as in (14) and choose D=diag(1.5, 0.5)D=diag(1.5,\,0.5) to satisfy W34⊤DW41+L13123=0W_34 DW_41+L^123_13=0, which removes edge 1,3\1,3\. We then initialize a 4d×4d4d× 4d zero matrix Lpad134(D)L^134_pad(D) and embed L134(D)L^134(D) into it by setting (a1,a2,a3)=(1,3,4)(a_1,a_2,a_3)=(1,3,4) and (Lpad134(D))abad=(L134(D))bd (L^134_pad(D) )_a_ba_d= (L^134(D) )_bd for b,d∈1,2,3b,d∈\1,2,3\. The updated Laplacian L+=ℰ(L123)+Lpad134(D)L^+=E(L_123)+L^134_pad(D) corresponds to the graph shown in Fig. 4(b), in which edge 1,3\1,3\ is eliminated and new edges 1,4,3,4\1,4\,\3,4\ appear. Vertices 5 and 6 are subsequently added using the same strategy: vertex 5 at p~5=[0,−2]⊤ p_5=[0,-2] (connected to 1 and 4, deleting 1,4\1,4\) with D=diag(2.5,0.3)D=diag(2.5,0.3), and vertex 6 at p~6=[−2,−3]⊤ p_6=[-2,-3] (connected to 1 and 5, deleting 1,5\1,5\) with D=diag(5,0.2)D=diag(5,0.2). Next, vertex 7 is added at p~7=[−1,−2.1]⊤ p_7=[-1,-2.1] using the triplet (i,j,v)=(5,6,7)(i,j,v)=(5,6,7) with D=diag(1,1)D=diag(1,1), following the agent joining operation, as illustrated in Fig. 4(e). Finally, edge 5,6\5,6\ is deleted by applying the edge removal operation with the same triplet (5,6,7)(5,6,7): we require L56+W67⊤DW75=0L_56+W_67 DW_75=0, giving D=diag(14,65.6667)D=diag(14,65.6667). The final cycle is shown in Fig. 4(f). (a) Agent trajectories. (b) Tracking errors. Figure 5: Formation maneuver control under agent joining (agent 77 joins at t=10t=10s, agent 88 joins at t=20t=20s). 5.2 Formation Maneuver Control with Agent Joining This simulation validates the proposed agent joining protocol (Algorithm 1) in a dynamic formation maneuver scenario. The initial six-agent formation is a cycle graph whose vertex set, edge set, and edge weight matrices are shown in Fig. 4(d). The Laplacian L of this formation satisfies the formation spectrum (Definition 3), as constructed in Section 5.1. The simulation timeline includes formation establishment (0–10 s), the integration of agent 7 at 1010 s, a non-uniform scaling maneuver (15–25 s), and the integration of agent 8 at 2020 s. As shown in Fig. 5(a), the initial six-agent formation achieves and maintains the desired shape during the establishment phase, using the nominal formation and Laplacian from Subsection 5.1. At t=10t=10 s, agent 7 joins at p~7=[−1,−2.1]⊤ p_7=[-1,-2.1] by executing Algorithm 1 with the triplet (5,6,7)(5,6,7) and D=I2D=I_2. This triggers a one-time distributed update of the Laplacian to L+L^+, which again satisfies the formation spectrum. From t=15t=15 s to t=25t=25 s, the formation performs a non-uniform scaling maneuver, compressing by 50% along the y-axis to navigate a narrow passage. This specific maneuver is necessary since uniform scaling or rigid-body motion would result in inter-agent collisions or an inability to pass through the constriction. At t=20t=20 s, during the active scaling, agent 8 joins at p~8=[−1,1]⊤ p_8=[-1,1] by executing Algorithm 1 with the triplet (2,3,8)(2,3,8) and D=I2D=I_2, testing the framework’s ability to handle simultaneous shape deformation and network expansion. Fig. 5 (b) shows that both leader tracking error and follower tracking error converge to zero, with only a minor transient disturbance during the agent joining event at 1010 s and 2020 s. (a) Agent trajectories. (b) Tracking errors. Figure 6: Formation maneuver control without agent leaving protocol (agent 66 halts at t=10t=10 s). (a) Agent trajectories. (b) Tracking errors. Figure 7: Formation maneuver control with proposed agent leaving protocol (agent 66 removed). (a) Agent trajectories. (b) Tracking errors. Figure 8: Formation maneuver control without edge removal protocol (edge 5,6\5,6\ disconnected at t=10t=10 s). (a) Agent trajectories. (b) Tracking errors. Figure 9: Formation maneuver control with proposed edge removal protocol (edge 5,6\5,6\ removed at t=10t=10 s). 5.3 Formation Maneuver Control with Agent Leaving This simulation validates the agent leaving protocol proposed in Section 4.3. The initial formation is a graph whose vertex set, edge set, and edge weight matrices are shown in Fig. 4(d). The Laplacian L of this formation satisfies the formation spectrum (Definition 3), as constructed in Section 5.1. The simulation consists of two phases: formation establishment (0–10 s) and agent leaving (10–30 s). At t=10t=10 s, agent 66 stops moving due to failure. (i.e., p6p_6 no longer changes), but the formation control law continues to run. Figures 6 and 7 compare the system behavior with and without the proposed agent leaving strategy. In Fig. 6, the Laplacian is left unchanged; we simply set the velocity of agent 66 to zero to simulate a failure, causing significant deformation and diverging tracking errors. In Fig. 7, we apply the agent leaving protocol: Δ¯=0 =0 and Δ=−Lu⊤Luu−1Lu =-L_u L_u^-1L_u with u=6u=6, yielding L+=ℰ(L+Δ)L^+=E(L+ ). The updated Laplacian corresponds to the five-agent graph in Fig. 4(c). Using L+L^+ in the control law, the remaining agents rapidly reconfigure into a consistent formation while keeping all tracking errors bounded. 5.4 Formation Maneuver Control with Edge Removal This simulation validates the edge removal protocol for Case (i) of Subsection 4.4, where H=G−eH=G-e remains 22-vertex-connected and no compensatory edges are needed (Eadd=∅E_add= ). The initial formation is a graph whose vertex set, edge set, and edge weight matrices are shown in Fig. 4(e). The Laplacian L of this formation satisfies the formation spectrum (Definition 3), as constructed in Section 5.1. The simulation consists of two phases: formation establishment (0–10 s) and edge removal (10–30 s). At t=10t=10 s, the relative displacement measurement of edge 5,6\5,6\ is lost. Figures 8 and 9 compare the system behavior with and without the proposed edge removal strategy. In Fig. 8, the Laplacian is left unchanged; the missing measurement is set to zero, leading to visible formation distortion and unbounded tracking errors. In Fig. 9, the proposed edge removal protocol is executed: using triplet (5,6,7)(5,6,7), we compute D=diag(14, 65.6667)D=diag(14,\;65.6667) to satisfy W67⊤DW75=−L56W_67 DW_75=-L_56, construct Δ=Lpad567(D) =L^567_pad(D) (as in (18)), and update the Laplacian to L+=L+ΔL^+=L+ , corresponding to the cycle graph in Fig. 4(f). The updated Laplacian maintains the formation spectrum; the formation rapidly converges again and tracking errors remain bounded. 6 Conclusion We have developed a distributed framework for non-uniform scaling formation maneuver control of open multi-agent systems. It handles four elementary topology operations—agent joining, agent leaving, edge addition, and edge removal—solving the spectral shaping problem of the matrix-valued Laplacian under topology changes. Rigorous theoretical analysis and simulation validation were provided. Several directions merit future investigation. Extending the proposed framework to directed graphs would broaden its applicability. Adaptive leader–follower reassignment and maneuver parameter generation based on environmental feedback present promising avenues. Graph augmentation under more complex constraints also warrants further study. Appendix A Proof of Theorem 1 The proof requires a lemma. Lemma 7 (Schur complement [17, 38]). For any symmetric block matrix of the form M=[ABB⊤C]M=[ smallmatrixA&B\\ B &C smallmatrix] where C is invertible, let S=A−BC−1B⊤S=A-BC^-1B denote the Schur complement of C in M. Then the following statements hold: (1) M is invertible if and only if S is invertible. In that case, M−1=[S−1−S−1BC−1−C−1B⊤S−1C−1+C−1B⊤S−1BC−1].M^-1= bmatrixS^-1&-S^-1BC^-1\\ -C^-1B S^-1&C^-1+C^-1B S^-1BC^-1 bmatrix. (2) M≻0M 0 if and only if C≻0C 0 and S≻0S 0. (3) If C≻0C 0, then M⪰0M 0 if and only if S⪰0S 0. We now prove Theorem 1. pf We first prove that L+L^+ has a formation spectrum by verifying the three conditions in Definition 3. (1) Proof of L+⪰0L^+ 0 (condition (i) of Definition 3). Since L⪰0L 0 and Lijv⪰0L^ijv 0, we have L+⪰0L^+ 0. (2) Proof of Q⊤L+Q≻0Q L^+Q 0 for every Q∈Q (condition (i) of Definition 3). For the specific leader set r1,r2r_1,r_2, this reduces to proving Lff+≻0L^+_f 0. To prove this, we consider two cases: v as a follower and v as a leader. The proof for other leader sets is analogous. Case A: v is added as a follower. For the detailed proof, see [16] (the preliminary version of this work). Case B: v is added as a leader. To maintain exactly two leaders, we replace one of the original leaders with v. Without loss of generality, we retain r1r_1 as a leader and demote r2r_2 to a follower. The new leader set is r1,v\r_1,v\, and the new follower set is Vf∪r2V_f∪\r_2\. We now consider all possible roles of the selected neighbours i,ji,j and show that the new follower block Lff+L^+_f is positive definite. Partition the new follower set into P1=Vf∖i,jP_1=V_f \i,j\ and P2=(Vf∪r2)∖P1P_2=(V_f∪\r_2\) P_1. Write Lff+=[ABB⊤C+ΔC],L^+_f= bmatrixA&B\\ B &C+ _C bmatrix, (41) where A=LP1P1≻0A=L_P_1P_1 0, C=LP2P2C=L_P_2P_2, and ΔC=Δ¯P2P2⪰0 _C= _P_2P_2 0. By the Schur complement lemma, Lff+≻0L^+_f 0 if and only if S+ΔC≻0S+ _C 0 with S=C−B⊤A−1B⪰0S=C-B A^-1B 0. Suppose there exists a nonzero y∈ker(S)∩ker(ΔC)y∈ (S)∩ ( _C). Then from y∈ker(S)y∈ (S), there exists x such that [ABB⊤C][xy]=0[ smallmatrixA&B\\ B &C smallmatrix][ smallmatrixx\\ y smallmatrix]=0. Define w on the original vertex set V by setting w|P1=xw|_P_1=x, w|P2=yw|_P_2=y, and wr1=0w_r_1=0. Because w⊤Lw=[xy][ABB⊤C][xy]=0w Lw=[ smallmatrixx\,y smallmatrix][ smallmatrixA&B\\ B &C smallmatrix][ smallmatrixx\\ y smallmatrix]=0 and L⪰0L 0, we have Lw=0Lw=0. Hence w lies in Π(p~,R) ( p,R), i.e., there exist S(R)S(R) and τ such that wk=τ+S(R)p~kw_k=τ+S(R) p_k for all k. With wr1=0w_r_1=0, we get τ=−S(R)p~r1τ=-S(R) p_r_1, and thus for any k∈P2k∈ P_2, wk=S(R)(p~k−p~r1).w_k=S(R)( p_k- p_r_1). (42) Now we examine each subcase, using the condition y∈ker(ΔC)y∈ ( _C) to derive a contradiction. Subcase B1: i=r1i=r_1, j=r2j=r_2. Here P2=r2P_2=\r_2\ and ΔC=Wvr1⊤DWvr1≻0 _C=W_vr_1 DW_vr_1 0, so ker(ΔC)=0 ( _C)=\0\. Hence no nonzero y exists. Subcase B2: i=r1i=r_1, j∈Vfj∈ V_f. Here P2=j,r2P_2=\j,r_2\ and ΔC=diag(Wvr1⊤DWvr1,0) _C=diag(W_vr_1 DW_vr_1,0) in the ordering (j,r2)(j,r_2). If y∈ker(ΔC)y∈ ( _C), then yj=0y_j=0. From (42), yj=S(R)(p~j−p~r1)y_j=S(R)( p_j- p_r_1), so p~j=p~r1 p_j= p_r_1. This contradicts the fact that j and r1r_1 are distinct agents, which is guaranteed by Assumption 1. Subcase B3: i∈Vfi∈ V_f, j=r2j=r_2. Here P2=i,r2P_2=\i,r_2\ and ΔC=[Wr2v⊤DWr2vWr2v⊤DWviWvi⊤DWr2vWvi⊤DWvi]. _C= bmatrixW_r_2v DW_r_2v&W_r_2v DW_vi\\ W_vi DW_r_2v&W_vi DW_vi bmatrix. (43) Its nullspace is ker(ΔC)=y=[yi,yr2]⊤:Wr2vyi+Wviyr2=0 ( _C)=\y=[y_i,y_r_2] :W_r_2vy_i+W_viy_r_2=0\. If y∈ker(ΔC)y∈ ( _C), then using (42) for i and r2r_2 and substituting into the nullspace condition yields after simplification (p~i,Rα−p~r2,Rα)(p~r1,Rα−p~v,Rα)=0∀α∈1,…,d.( p_i,R^α- p_r_2,R^α)( p_r_1,R^α- p_v,R^α)=0 ∀α∈\1,…,d\. (44) By Assumption 1, p~ir2,R p_ir_2,R has all components nonzero, so p~i,Rα≠p~r2,Rα p_i,R^α≠ p_r_2,R^α. Hence p~r1,Rα=p~v,Rα p_r_1,R^α= p_v,R^α for all α, i.e., p~r1=p~v p_r_1= p_v, contradicting that v is a new agent with distinct nominal position (can be ensured by choice). Thus no such y exists. Subcase B4: i,j∈Vfi,j∈ V_f. Here P2=i,j,r2P_2=\i,j,r_2\ and ΔC _C affects the (i,j,r2)(i,j,r_2) block. Its nullspace is ker(ΔC)=y=[yi,yj,yr2]⊤:Wjvyi+Wviyj=0 ( _C)=\y=[y_i,y_j,y_r_2] :W_jvy_i+W_viy_j=0\. If y∈ker(ΔC)y∈ ( _C), then using (42) for i,j,r2i,j,r_2 and substituting into the nullspace condition yields after simplification (p~i,Rα−p~j,Rα)(p~r1,Rα−p~v,Rα)=0∀α∈1,…,d.( p_i,R^α- p_j,R^α)( p_r_1,R^α- p_v,R^α)=0 ∀α∈\1,…,d\. (45) By Assumption 1, p~ji,R p_ji,R has all components nonzero, so p~i,Rα≠p~j,Rα p_i,R^α≠ p_j,R^α. Hence p~r1,Rα=p~v,Rα p_r_1,R^α= p_v,R^α for all α, i.e., p~r1=p~v p_r_1= p_v, again a contradiction. In all subcases, no nonzero y∈ker(S)∩ker(ΔC)y∈ (S)∩ ( _C) exists. Therefore S+ΔC≻0S+ _C 0, and consequently Lff+≻0L^+_f 0. (3) Proof of ker(L+)=Π(p~+,R) (L^+)= ( p^+,R) (condition (i) of Definition 3). First, by construction and Lemma 5, any p+∈Π(p~+,R)p^+∈ ( p^+,R) satisfies: ℰ(L)p+=0andLpadijvp+=0,E(L)p^+=0 L^ijv_padp^+=0, (46) implying that L+p+=0L^+p^+=0. This shows Π(p~+,R)⊆ker(L+) ( p^+,R) (L^+). For the reverse inclusion, note that Lff+≻0L^+_f 0 (proved above) and Lff+∈ℝd(n−1)×d(n−1)L^+_f ^d(n-1)× d(n-1) imply rank(L+)≥d(n−1)rank(L^+)≥ d(n-1). Since p~+ p^+ contains p~ p as a subvector, the projection π:ℝd(n+1)→ℝdnπ:R^d(n+1) ^dn onto the first n agents satisfies π(Π(p~+,R))=Π(p~,R)π( ( p^+,R))= ( p,R). As dim(Π(p~,R))=2d ( ( p,R))=2d and π is surjective onto it, we have dim(Π(p~+,R))≥2d ( ( p^+,R))≥ 2d. Every element of Π(p~+,R) ( p^+,R) is parameterized by (s,τ)∈ℝ2d(s,τ) ^2d, so dim(Π(p~+,R))≤2d ( ( p^+,R))≤ 2d. Hence dim(Π(p~+,R))=2d ( ( p^+,R))=2d. Consequently, rank(L+)≤d(n+1)−2d=d(n−1)rank(L^+)≤ d(n+1)-2d=d(n-1), which together with the lower bound gives rank(L+)=d(n−1)rank(L^+)=d(n-1) and dim(ker(L+))=2d ( (L^+))=2d. The inclusion Π(p~+,R)⊆ker(L+) ( p^+,R) (L^+) together with dim(Π(p~+,R))=dim(ker(L+))=2d ( ( p^+,R))= ( (L^+))=2d implies ker(L+)=Π(p~+,R) (L^+)= ( p^+,R). (4) Proof of minimality of |Eadd||E_add| and |Emod||E_mod|. We choose D≻0D 0 such that Lij+Wjv⊤DWvi≠0L_ij+W_jv DW_vi≠ 0. By Assumption 1, WjvW_jv and WviW_vi are invertible. Consequently, the construction of L+L^+ in (16) adds precisely two new edges i,v\i,v\ and j,v\j,v\ (whose weights are non-zero), while preserving the existing edge i,j\i,j\ and leaving all other edges unchanged. Hence E+=E∪EaddE^+=E∪ E_add, and Emod=i,jE_mod=\\i,j\\. We now verify that |Eadd||E_add| is minimal while ensuring G+G^+ remains 2-vertex-connected. Note that L+L^+ is symmetric, so G+G^+ is undirected. Adding only one edge i,v\i,v\, would violate 2-vertex-connectivity because removing i would isolate v. Hence at least two edges are necessary. To verify that G+G^+ with EaddE_add indeed preserves 2-vertex-connectedness, remove any vertex x∈V+x∈ V^+. If x=vx=v, the remaining graph is G, which is connected. If x∈Vx∈ V and x≠i,jx≠ i,j, then G−xG-x contains a connected subgraph with i,ji,j; since v connects to both, G+−xG^+-x remains connected. If x=ix=i (or symmetrically x=jx=j), G−iG-i is connected and contains j; with v connected to j, G+−iG^+-i stays connected. Thus G+G^+ is 2-vertex-connected. To establish minimality of |Emod||E_mod|, suppose |Emod|=0|E_mod|=0. Then L+=ℰ(L)+Δ¯L^+=E(L)+ with Δ¯≠0 ≠ 0 only affects rows and columns of v. Since L+L^+ and ℰ(L)E(L) are symmetric, Δ¯ is symmetric. For any p∈Π(p~+,R)p∈ ( p^+,R), L+p=ℰ(L)p=0L^+p=E(L)p=0, hence Δ¯p=0 p=0. Choose p=n+1⊗τp=1_n+1 τ with τ≠0τ≠ 0. Then Δ¯ivτ=0 _ivτ=0 for all τ and any i∈Vi∈ V, forcing Δ¯iv=0 _iv=0. By symmetry, Δ¯vi=0 _vi=0 for any i∈Vi∈ V, thus Δ¯=0 =0, contradicting Δ¯≠0 ≠ 0. Therefore |Emod|≥1|E_mod|≥ 1. Our construction achieves |Emod|=1|E_mod|=1, which is minimal. References [1] M. Ahmadi and P. Stone (2006) Keeping in touch: maintaining biconnected structure by homogeneous robots. In Proceedings of the 21st National Conference on Artificial Intelligence, Boston, Massachusetts, p. 580–585. Cited by: Remark 5. [2] I. Buckley and M. Egerstedt (2021) Infinitesimal shape-similarity for characterization and control of bearing-only multirobot formations. IEEE Transactions on Robotics 37 (6), p. 1921–1935. Cited by: Table 1, §1, Remark 1. [3] H. Cao, H. Zhang, and L. Xie (2025) Synchronization acceleration of networked systems via edge addition to single-root weighted digraphs. IEEE Transactions on Automatic Control 70 (3), p. 1730–1744. Cited by: Table 1, §1, §1. [4] K. Cao, Z. Han, X. Li, and L. Xie (2020) Ratio-of-distance rigidity theory with application to similar formation control. IEEE Transactions on Automatic Control 65 (6), p. 2598–2611. Cited by: Table 1, §1, Remark 1, Remark 4. [5] L. Chen, M. Cao, and C. Li (2021) Angle rigidity and its usage to stabilize multiagent formations in 2-D. IEEE Transactions on Automatic Control 66 (8), p. 3667–3681. Cited by: Table 1, §1, Remark 4. [6] J. A. De Loera, J. Rambau, and F. Santos (2010) Triangulations. Springer Berlin Heidelberg. Cited by: §4.2.2, §4.2.2. [7] R. Diestel (2017) Graph theory. Springer Berlin Heidelberg. Cited by: Definition 1. [8] J. Erskine, S. Briot, I. Fantoni, and A. Chriette (2024) Singularity analysis of rigid directed bearing graphs for quadrotor formations. IEEE Transactions on Robotics 40 (), p. 139–157. Cited by: Remark 1. [9] K. P. Eswaran and R. E. Tarjan (1976) Augmentation problems. SIAM Journal on Computing 5 (4), p. 653–665. Cited by: Remark 5, Remark 6. [10] X. Fang and L. Xie (2024) Distributed formation maneuver control using complex laplacian. IEEE Transactions on Automatic Control 69 (3), p. 1850–1857. Cited by: Table 1, §1, §1. [11] K. Fathian, N. R. Gans, W. Z. Krawcewicz, and D. I. Rachinskii (2019) Regular polygon formations with fixed size and cyclic sensing constraint. IEEE Transactions on Automatic Control 64 (12), p. 5156–5163. External Links: Document Cited by: Remark 4. [12] M. Franceschelli and P. Frasca (2021) Stability of open multiagent systems and applications to dynamic consensus. IEEE Transactions on Automatic Control 66 (5), p. 2326–2331. Cited by: §1. [13] H. Garcia de Marina (2021) Distributed formation maneuver control by manipulating the complex laplacian. Automatica 132, p. 109813. Cited by: Table 1, §1, §1. [14] G. He, G. Jing, and Y. Song (2025) Global stabilization of similar formation via edge-based clique addition. Automatica 173, p. 112084. Cited by: Remark 1. [15] T. He and G. Jing (2026) Distributed non-uniform scaling control of multi-agent formation via matrix-valued constraints. IEEE Transactions on Automatic Control (), p. 1–16. External Links: Document Cited by: §1, §2.4, §4, Lemma 3, Lemma 5, Remark 2. [16] T. He and G. Jing (2026) Distributed non-uniform scaling control of multi-agent formation with dynamic agent joining. Note: arXiv:2605.29191 Cited by: Appendix A, §5, Laplacian Spectral Shaping for Non-Uniform Scaling Formation Control of Open Multi-Agent Systems. [17] R. A. Horn and C. R. Johnson (2013) Matrix analysis. Cambridge University Press. Cited by: Lemma 7. [18] Z. Jia, M. Chi, Z. Liu, and G. Wen (2026) Nondisruptive consensus in discrete-time open multiagent systems with double integrator dynamics. IEEE Transactions on Automatic Control 71 (3), p. 2093–2100. Cited by: §1. [19] G. Jing, G. Zhang, H. W. J. Lee, and L. Wang (2019) Angle-based shape determination theory of planar graphs with application to formation stabilization. Automatica 105, p. 117–129. Cited by: Table 1, §1, §2.2, Remark 4. [20] A. Karimian and R. Tron (2017) Theory and methods for bearing rigidity recovery. In Proceedings of IEEE 56th Annual Conference on Decision and Control, Melbourne, VIC, Australia, p. 2228–2235. Cited by: Table 1, §1. [21] H. Li, H. Chen, X. Wang, Z. Li, and L. Shen (2026) Distributed framework construction for affine formation control. IEEE Transactions on Automatic Control 71 (1), p. 243–258. Cited by: Table 1, §1, §1, Remark 3, Remark 5. [22] Y. Li and W. Dong (2024) Flexible affine formation control based on dynamic hierarchical reorganization. IEEE Robotics and Automation Letters 9 (12), p. 11290–11297. External Links: Document Cited by: §2.4. [23] Z. Lin, L. Wang, Z. Han, and M. Fu (2014) Distributed formation control of multi-agent systems using complex laplacian. IEEE Transactions on Automatic Control 59 (7), p. 1765–1777. Cited by: Table 1, §1, §1, §2.2, Definition 2, Remark 2. [24] Z. Lin, L. Wang, Z. Chen, M. Fu, and Z. Han (2016) Necessary and sufficient graphical conditions for affine formation control. IEEE Transactions on Automatic Control 61 (10), p. 2877–2891. Cited by: Table 1, §1. [25] B. Liu, T. Chu, L. Wang, and G. Xie (2008) Controllability of a leader–follower dynamic network with switching topology. IEEE Transactions on Automatic Control 53 (4), p. 1009–1013. Cited by: §1. [26] P. Mukherjee, M. Santilli, A. Gasparri, and R. K. Williams (2020) Optimal topology selection for stable coordination of asymmetrically interacting multi-robot systems. In Proceedings of 2020 IEEE International Conference on Robotics and Automation, Paris, France, p. 6668–6674. Cited by: Remark 3. [27] K. Oh, M. Park, and H. Ahn (2015) A survey of multi-agent formation control. Automatica 53, p. 424–440. External Links: Document Cited by: Table 1, §1. [28] A. Rosenthal and A. Goldner (1977) Smallest augmentations to biconnect a graph. SIAM Journal on Computing 6 (1), p. 55–66. Cited by: Remark 5, Remark 6. [29] F. Sahebsara and M. de Queiroz (2024) On the stability of distance-based formation control with minimally globally rigid graphs. Systems & Control Letters 185, p. 105726. Cited by: Remark 4. [30] P. Sekercioglu, A. Fontan, and D. V. Dimarogonas (2025) Stability of open multi-agent systems over dynamic signed graphs. In Proceedings of the 64th IEEE Conference on Decision and Control, Rio de Janeiro, Brazil, p. 7172–7177. Cited by: §1. [31] S. Sun, X. Wang, D. Sanalitro, A. Franchi, M. Tognon, and J. Alonso-Mora (2025) Agile and cooperative aerial manipulation of a cable-suspended load. Science Robotics 10 (107), p. eadu8015. Cited by: §1. [32] M. H. Trinh, Q. Van Tran, and H. Ahn (2020) Minimal and redundant bearing rigidity: conditions and applications. IEEE Transactions on Automatic Control 65 (10), p. 4186–4200. Cited by: Table 1, §1, §1, §2.2. [33] H. M. Vu, M. H. Trinh, Q. V. Tran, and H. S. Ahn (2024) Distance-based formation tracking of single- and double-integrator agents. IEEE Transactions on Automatic Control 69 (2), p. 1332–1339. Cited by: Table 1, §1. [34] Q. Wang, G. Nie, Y. Tian, and H. Tian (2026) LADAR: low-latency distributed articulation point detection and mobility recovery for FANETs. In Proceedings of the 11th International Conference on Communication and Information Processing, New York, NY, USA, p. 34–39. Cited by: §4.4. [35] F. Xiao, Q. Yang, X. Zhao, and H. Fang (2022) A framework for optimized topology design and leader selection in affine formation control. IEEE Robotics and Automation Letters 7 (4), p. 8627–8634. Cited by: Remark 3. [36] Q. Yang, M. Cao, and B. D. O. Anderson (2019) Growing super stable tensegrity frameworks. IEEE Transactions on Cybernetics 49 (7), p. 2524–2535. Cited by: Remark 3. [37] C. Yu, B. Fidan, J. M. Hendrickx, and B. D.O. Anderson (2006) Merging multiple formations: a meta-formation prospective. In Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, CA, USA, p. 4657–4663. Cited by: Table 1, §1. [38] F. Zhang (2005) The Schur complement and its applications. Springer New York, NY, New York,USA. Cited by: Lemma 7. [39] Y. Zhang, S. Oğuz, S. Wang, E. Garone, X. Wang, M. Dorigo, and M. K. Heinrich (2024) Self-reconfigurable hierarchical frameworks for formation control of robot swarms. IEEE Transactions on Cybernetics 54 (1), p. 87–100. Cited by: Table 1, §1. [40] S. Zhao and D. Zelazo (2016) Bearing rigidity and almost global bearing-only formation stabilization. IEEE Transactions on Automatic Control 61 (5), p. 1255–1268. Cited by: Table 1, §1. [41] S. Zhao (2018) Affine formation maneuver control of multiagent systems. IEEE Transactions on Automatic Control 63 (12), p. 4140–4155. Cited by: Table 1, §1, §1, Remark 1. [42] X. Zhou, X. Wen, Z. Wang, Y. Gao, H. Li, Q. Wang, T. Yang, H. Lu, Y. Cao, C. Xu, and F. Gao (2022) Swarm of micro flying robots in the wild. Science Robotics 7 (66), p. eabm5954. Cited by: §1. [43] H. Zhu, J. Juhl, L. Ferranti, and J. Alonso-Mora (2019) Distributed multi-robot formation splitting and merging in dynamic environments. In Proceedings of 2019 International Conference on Robotics and Automation, Montreal, QC, Canada, p. 9080–9086. Cited by: Table 1, §1. [44] W. Zhu, S. Oğuz, M. K. Heinrich, M. Allwright, M. Wahby, A. L. Christensen, E. Garone, and M. Dorigo (2024) Self-organizing nervous systems for robot swarms. Science Robotics 9 (96), p. eadl5161. Cited by: §1.