Large digraphs with small diameter: A voltage assignment approach

Abstract

<p>The theory of lifting voltage digraphs provides a useful tool for constructing large digraphs with given properties from suitable small base digraphs endowed with an assignment of voltages (=elements of a finite group) on arcs. We revisit the degree/diameter problem for digraphs from this new perspective and prove a general upper bound on diameter of a lifted digraph in terms of properties of the base digraph and voltage assignment. In addition, we show that all currently known largest vertex-transitive Cayley digraphs for semidirect products of groups can be described by means of a voltage assignment construction using simpler groups.</p>