The Open UniversitySkip to content
 

Digraphs with degree two and excess two are diregular

Tuite, James (2019). Digraphs with degree two and excess two are diregular. Discrete Mathematics, 342(5) pp. 1233–1244.

DOI (Digital Object Identifier) Link: https://doi.org/10.1016/j.disc.2019.01.010
Google Scholar: Look up in Google Scholar

Abstract

A k-geodetic digraph with minimum out-degree d has excess ϵ if it has order M(d,k)+ϵ, where M(d,k) represents the Moore bound for out-degree d and diameter k. For given ϵ, it is simple to show that any such digraph must be out-regular with degree d for sufficiently large d and k. However, proving in-regularity is in general non-trivial. It has recently been shown that any digraph with excess ϵ=1 must be diregular. In this paper we prove that digraphs with minimum out-degree d=2 and excess ϵ=2 are diregular for k≥2.

Item Type: Journal Item
ISSN: 0012-365X
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Related URLs:
Item ID: 58923
Depositing User: ORO Import
Date Deposited: 30 Jan 2019 14:07
Last Modified: 07 May 2019 12:50
URI: http://oro.open.ac.uk/id/eprint/58923
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU