2025/07/01 by Haejoon Lee, Dimitra Panagou, Lee, Haejoon +1 · 1 citation
Computer Science · Engineering · #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Electrical engineering #Smart Grid Security and Resilience #Social and Information Networks (cs.SI) #Stability and Control of Uncertain Systems #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2507.00415
openalex publication_date 2025/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The notions of r-robustness and (r,s)-robustness of a network have been earlier introduced in the literature to achieve resilient consensus in the presence of misbehaving agents. However, while higher robustness levels enable networks to tolerate a higher number of misbehaving agents, they also require dense communication structures, which are not always desirable for systems with limited communication ranges, energy, and resources. Therefore, this paper studies the fundamental structures behind r-robustness and (r,s)- robustness properties in two ways. (a) We first establish tight necessary conditions on the number of edges that an undirected graph with an arbitrary number of nodes must have to achieve maximum r- and (r,s)-robustness. (b) We then use these conditions to construct two classes of undirected graphs, referred as to γ- and (γ,γ)-Minimal Edge Robust Graphs (MERGs), that provably achieve maximum robustness with minimal numbers of edges. We demonstrate the effectiveness of our method via comparison against existing robust graph structures and a set of simulations.