On diregular digraphs with degree two and excess two

Tuite, James (2018). On diregular digraphs with degree two and excess two. Discrete Applied Mathematics, 238 pp. 167–174.

DOI: https://doi.org/10.1016/j.dam.2017.10.034


An important topic in the design of efficient networks is the construction of (d, k, +Є)- digraphs, i.e. k-geodetic digraphs with minimum out-degree ≥ d and order M(d,k)+ Є, where M(d,k) represents the Moore bound for degree d and diameter k and Є > 0 is the (small) excess of the digraph. Previous work has shown that there are no (2, k,+1)-digraphs for k ≥ 2. In a separate paper, the present author has shown that any (2, k,+2)-digraph must be diregular for k ≥ 2. In the present work, this analysis is completed by proving the nonexistence of diregular (2, k,+2)-digraphs for k ≥ 3 and classifying diregular (2,2,+2)-digraphs up to isomorphism.

Viewing alternatives

Download history


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions