On the Total Regularity of Almost Mixed Moore Graphs

Abstract

The degree/diameter problem asks for the largest order of a graph with a given diameter and maximum vertex degree. This has been widely studied and given rise to a recent variation for mixed graphs (graphs with both undirected edges and directed arcs), where an additional bound is placed on the maximum directed out-degree of any vertex. Both problems have applications to network design. Counting the possible number of vertices at each distance from a given vertex gives a bound on the order of a mixed graph satisfying the degree and diameter constraints (the mixed Moore bound). In this paper, we settle an open problem posed by Tuite and Erskine concerning the total regularity of mixed graphs whose order is one less than the mixed Moore bound (almost mixed Moore graphs). We use this result to show that the three known almost mixed Moore graphs of diameter at least three are the only such mixed graphs.