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.
Collections
Related items
Showing items related by title, author, creator and subject.
-
An Exploration of Orthogonal Colourings
MacKeigan, Kyle (2021-09-01)Two colourings of a graph are orthogonal if when two elements are coloured with the same colour in one of the colourings, then those elements receive distinct colours in the other colouring. First, we study the orthogonal ... -
Uniform Embedding of Robinson Similarity Matrices
Zhang, Zhiyuan (2021-04-30)A Robinson similarity matrix is a symmetric matrix where the entry values on all rows and columns increase toward the diagonal. Decompose the Robinson matrix into the sum of k {0, 1}-matrices, then these k {0, 1}-matrices ... -
A Distributed Method for Fast Force-Directed Layout of Large Scale-free Network Graphs
Lapierre, Nathan (2016-01-07)Network graphs from Online Social Networks (OSNs) - representing network participants, and their relationships and interactions - are an area of significant investigation. Visual layouts of these graphs are a common tool ...