The Average Connectivity of a Family of Expander Graphs

Patrick Bahls1
1Department of Mathematics University of North Carolina, Asheville, NC 28804

Abstract

We compute the limiting average connectivity \(\overline{\kappa}\) of the family of \(3\)-regular expander graphs whose members are formed from the finite fields \(\mathbb{Z}_p\), by connecting every \(x \in \mathbb{Z}_p\) with \(x\pm1\) and \(x^{-1}\), all computations performed modulo \(p\). Namely, we show

\[\lim_{p\to\infty} \overline{\kappa}(\mathbb{Z}_p) = 3\]

for primes \(p\). We compare this behavior with an upper bound on the expected value of \(\overline{\kappa}(\mathbb{Z}_n)\) for a more general class \(\{\mathbb{Z}_n\}_{n\in\mathbb{N}}\) of related graphs.