'Plug-and-Play' Style Connection Methods for Graphs with an Application in Expanding Multiagent Consensus Networks

Multiagent consensus systems are commonly studied in regard to their scalability and performance. Their scalability relies heavily on the underlying communication system and its connectivity. While it is possible to generate a random graph, which exhibits almost surely good connectivity even with a large number of agents, in a 'plug-and-play' setting, where agents should be able to connect and disconnect with minimal interruption, the generation of a new communication network, i.e., graph, each time an agent connects is not feasible. Rather, nodes will be added to the graph over time. In this article, we investigate methods to grow a graph, i.e., add nodes in a graph. We enforce that an upper bound on the maximum degree within the graph is maintained and that only new connections are established with the connecting node without affecting the remainder of the network. The latter condition is to avoid reconfiguration of the network, which reduces the necessary changes and allows the use in a plug-and-play setting. We find conditions on the ability to connect nodes. Furthermore, we study different connection strategies and their impact on the connectivity of the grown graph.