The Open UniversitySkip to content
 

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 (Digital Object Identifier) Link: https://doi.org/10.1016/j.dam.2019.02.045
Google Scholar: Look up in Google Scholar

Abstract

Moore digraphs, that is digraphs with out-degree d, diameter k and order equal to the Moore bound M(d, k) = 1 + d + d2 + · · · + dk, 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.

Item Type: Journal Item
Copyright Holders: 2019 Elsevier
ISSN: 0166-218X
Keywords: Degree/diameter problem; Digraphs; Excess; k-geodetic; Extremal digraphs
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 66734
Depositing User: ORO Import
Date Deposited: 17 Sep 2019 12:10
Last Modified: 03 Oct 2019 12:31
URI: http://oro.open.ac.uk/id/eprint/66734
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU