Voltage construction of highly-connected cubic graphs

Abstract

In this thesis we consider the spectrum and Algebraic Connectivity (AC) of cubic graphs that have representation as voltage graphs. These graphs have relatively high symmetry and often turn out to have high AC. We first discuss how to compute the full spectrum of a general voltage graph over the group $\mathbb{Z}_N$. This includes, for example, the Tutte-Coxeter graph. We then use voltage construction to search for cubic graphs with high AC and fixed number of vertices $n$, constructed from a base graph having at most four vertices. We were able to reproduce known records for $n\le 10$ and $n=14, 16, 18, 24, 26, 30, 40, 48, 50, 60.$ Moreover, we found a new record of a high-AC graph when $n=36, 46$ and $52$. In particular, the record for $n=36$ gives a counter-example to conjecture 6.1 proposed in \cite{kolokolnikov2023} which states that the graph with the maximal AC also has the highest girth.