Almost Moore digraphs are diregular

An almost Moore digraph is a digraph of diameter k⩾2, maximum out-degree d⩾2 and order n=d+d 2+⋯+d k , that is, one less than the Moore bound. It is easy to show that the out-degree of an almost Moore digraph is constant (=d). In this note we prove that also the in-degree of an almost Moore digraph...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2000-05, Vol.218 (1), p.265-270
Main Authors: Miller, Mirka, Gimbert, Joan, Širáň, Jozef, Slamin
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An almost Moore digraph is a digraph of diameter k⩾2, maximum out-degree d⩾2 and order n=d+d 2+⋯+d k , that is, one less than the Moore bound. It is easy to show that the out-degree of an almost Moore digraph is constant (=d). In this note we prove that also the in-degree of an almost Moore digraph is constant (=d), that is, every almost Moore digraph is diregular of degree d.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(99)00357-X