View PDF HTML (experimental)

Abstract: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 to as $\gamma$- and $(\gamma,\gamma)$-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.

Submission history

From: Haejoon Lee [view email]
[v1] Tue, 1 Jul 2025 04:04:48 UTC (3,413 KB)
[v2] Fri, 27 Feb 2026 02:53:08 UTC (3,295 KB)
[v3] Fri, 4 Sep 2026 14:41:11 UTC (3,278 KB)