4-minimal perfect critical sets graph structure in intelligent swarm with Laplace controllability

One of the primary objectives in studying natural biological swarms and multi-agent systems is to facilitate the emergence of "swarm intelligence."

Controllability is the fundamental issue in the field of control of multi-agent systems, and selecting the minimum number of leaders holds significant importance for improving control efficiency and reducing costs.

Laplacian controllability is a special type of structural controllability where the matrices used in Kalman controllability are replaced by the Laplacian matrices. This concept was first introduced by Tanner in 2004.

A recent research direction focuses on selecting the minimum number of leaders by analyzing the subgraph structure of undirected graph G. Currently, the graphical structures commonly used in studying the leader selection problem for undirected graphs include: Cactus, ZFS (zero forcing sets), CM (constraint matching), Dominating sets (DS), AEP (almost equitable partitions), et al. In this paper, we approach the problem using MPCS (minimal perfect critical sets) et al.

Unlike existing methods, this work introduced a novel approach to construct minimum leader sets for Laplacian controllability in undirected graphs by leveraging the concept of MPCS.

Our theoretical analysis confirmed that any leader set guaranteeing Laplacian controllability must intersect every MPCS. This result underscored the critical importance of characterizing all MPCSs in a graph as a key research objective. Through a comprehensive examination of all possible configurations of G[S] (where |S| = 4) in conjunction with the definition of MPCS, we rigorously established the theoretical framework for characterizing 4-MPCS. This systematic approach not only established a rigorous theoretical framework but also layed the technical foundation for investigating k-MPCS graphical structures where k≥5。

First, we develop a graph-theoretic framework integrated with algebraic techniques to rigorously characterize the substructure properties of MPCS. Subsequently, we establish a complete classification by proving the existence of exactly 21 distinct graphical configurations for 4-MPCS and provide their exhaustive structural characterization.

This paper presents a systematic investigation into the graph-theoretic properties of 4-MPCS for determining minimum leader sets in Laplacian-based controllability of multi-agent systems.

Our key contribution establishes a unified analytical framework that rigorously characterizes all 21 possible 4-MPCS configurations, providing both theoretical foundations and practical insights for controllability analysis. While the developed methodology is theoretically extendable to general k-MPCS cases, we identify fundamental computational limitations that currently restrict practical applications to small-scale systems.

The exhaustive classification of these fundamental substructures provides substantial theoretical and practical contributions to network controllability optimization. Importantly, this work reveals several critical open problems: (ⅰ) the structural characterization of MPCS in specialized graph families (e.g., tree networks, and chain topologies), and (ⅱ) the formulation of systematic graph design methodologies for minimal leaders selection, leveraging the intrinsic properties of MPCS to achieve Minimum Leader Set cardinality.