Jumat, 07 Maret 2014 - 20:31:27 WIB
On diregularity of digraphs of defect at most two
Dafik, Mirka Miller, Costas Iliopoulos, Zdenek Ryjacek; Proceedings of the eighteenth International Workshop on Combinatorial Algoritms,18 (2007) 39 - 48


Abstract: Since Moore digraphs do not exist for k /= 1 and d /= 1, the problem of finding the existence of digraph of out-degree d >= 2 and diameter k >= 2 and order close to the Moore bound becomes an interesting problem. To prove the non-existence of such digraphs, we first may wish to establish their diregularity. It is easy to show that any digraph with out-degree at most d >= 2, diameter k >= 2 and order n = d + d^2 + .... + d^{k-1}, that is, 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 out-regular and almost in-regular.

Key Words: Diregularity, digraph of defect two, degree-diameter problem.

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