Minggu, 29 Juni 2014 - 22:15:09 WIB
On Diregularity of Digraphs of Defect at Most Two
Dafik, Mirka Miller, Costas Iliopoulus, Zdenek Ryjacek, The Journal of Combinatorial Mathematics and Combinatorial Computing, 71 (2009) 21-37
Jurnal Internasional

Abstract

Abstract: 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.

Key Words:Diregularity, digraph of defect at most two


.:: Welcome to Prof. Dafik M.Sc,Ph.D Academic Website ::.