Paper Info
Title
On The Connectivity Of Unions Of Random Graphs
Abstract
Graph-theoretic tools and techniques have seen wide use in the multi-agent systems literature, and the unpredictable nature of some multi-agent communications has been successfully modeled using random communication graphs. Across both network control and network optimization, a common assumption is that the union of agents' communication graphs is connected across any finite interval of some prescribed length, and some convergence results explicitly depend upon this length. Despite the prevalence of this assumption and the prevalence of random graphs in studying multi-agent systems, to the best of our knowledge, there has not been a study dedicated to determining how many random graphs must be in a union before it is connected. To address this point, this paper solves two related problems. The first bounds the number of random graphs required in a union before its expected algebraic connectivity exceeds the minimum needed for connectedness. The second bounds the probability that a union of random graphs is connected. The random graph model used is the Erdos-Renyi model, and, in solving these problems, we also bound the expectation and variance of the algebraic connectivity of unions of such graphs. Numerical results for several use cases are given to supplement the theoretical developments made.
Year
DOI
Venue
2017
10.1109/cdc.2017.8264311
2017 IEEE 56TH ANNUAL CONFERENCE ON DECISION AND CONTROL (CDC)
Field
DocType
ISSN
Discrete mathematics,Random regular graph,Modular decomposition,Mathematical optimization,Indifference graph,Random graph,Clique-sum,Chordal graph,Cograph,Mathematics,Maximal independent set
Conference
0743-1546
Citations 
PageRank 
References 
1
0.47
5
Authors
1
Name
Order
Citations
PageRank
Hale, M.T.1176.84