Minimal Construction of Graphs with Maximum Robustness
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910034449924096 |
|---|---|
| author | Lee, Haejoon Panagou, Dimitra |
| author_facet | Lee, Haejoon Panagou, Dimitra |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00415 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimal Construction of Graphs with Maximum Robustness Lee, Haejoon Panagou, Dimitra Systems and Control Social and Information Networks 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. |
| title | Minimal Construction of Graphs with Maximum Robustness |
| topic | Systems and Control Social and Information Networks |
| url | https://arxiv.org/abs/2507.00415 |