A Note on Constructing Large Cayley Graphs of Given Degree and Diameter by Voltage Assignments

Abstract

<p>Voltage graphs are a powerful tool for constructing large graphs (called <i>lifts</i>) with prescribed properties as covering spaces of small <i>base</i> graphs. This makes them suitable for application to the <i>degree</i>/<i>diameter problem</i>, which is to determine the largest order of a graph with given degree and diameter.</p> <p>Many currently known largest graphs of degree ≤15 and diameter ≤10 have been found by computer search among Cayley graphs of semidirect products of cyclic groups. We show that <i>all</i> of them can in fact be described as lifts of smaller Cayley graphs of cyclic groups, with voltages in (other) cyclic groups. This opens up a new possible direction in the search for large vertex-transitive graphs of given degree and diameter.</p>