On diregular digraphs with degree two and excess three

Tuite, James (2019). On diregular digraphs with degree two and excess three. Discrete Applied Mathematics, 266 pp. 331–339.

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

Abstract

Moore digraphs, that is digraphs with out-degree d, diameter k and order equal to the Moore bound M(d, k) = 1 + d + d² + · · · + d^k, arise in the study of optimal network topologies. In an attempt to find digraphs with a ‘Moore-like’ structure, attention has recently been devoted to the study of small digraphs with minimum out-degree d such that between any pair of vertices u, v there is at most one directed path of length ≤ k from u to v; such a digraph has order M(d, k)+ϵ for some small excess ϵ. Sillasen et al. have shown that there are no digraphs with minimum out-degree two and excess one (Miller et al., 2018; Sillasen, 2015). The present author has classified all digraphs with out-degree two and excess two (Tuite, 2016, 2018). In this paper it is proven that there are no diregular digraphs with out-degree two and excess three for k ≥ 3, thereby providing the first classification of digraphs with order three away from the Moore bound for a fixed out-degree.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI