Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/916945

OpenURL Link
Title
On diregularity of digraphs of defect at most two
Author/Creator
Dafik;  Miller, Mirka;  Iliopoulos, Costas;  Ryjacek, Zdenek
Institution
The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description
Since Moore digraphs do not exist for k ≠ 1 and d ≠ 1, the problem of finding digraphs of out-degree d ≥ 2, diameter k ≥ 2 and order close to the Moore bound, becomes an interesting problem. To prove the non-existence of such digraphs or to assist in their construction (if they exist), we first may wish to establish some properties that such digraphs must possess. In this paper we consider the diregularity of such digraphs. It is easy to show that any digraph with out-degree at most d ≥ 2, diameter k ≥ 2 and order one or two less than Moore bound must have all vertices of out-degree d. However, establishing the regularity or otherwise of the in-degree of such a digraph is not easy. In this paper we prove that all digraphs of defect two are either diregular or almost diregular. Additionally, in the case of defect one we present a new, simpler and shorter, proof that a digraph of defect one must be diregular, and in the case of defect two and for d = 2 and k ≥ 3, we present an alternative proof that a digraph of defect two must be diregular.
Relation
Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, p. 21-37
Relation
http://www.charlesbabbage.org
Date
2009
Publisher
Charles Babbage Research Centre
Keyword(s)
digraphs;  diregularity;  regularity;  defect
Resource Type
journal article
Identifier
http://hdl.handle.net/1959.13/916945
Identifier
ISSN:0835-3026
Reviewed
Reviewed
14 Visitors 16 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"Journal of Combinatorial Mathematics and Combinatorial Computing"
 
OR