The Absorbant Number of Generalized de Bruijn Digraphs

Abstract

Let D = (V, A) be a digraph with the vertex set V and the arc set A. An absorbant of D is a set S subset of V such that for each v is an element of VS, O(v) boolean AND S not equal empty set where O(v) is the out-neighborhood of v. The absorbant number of D, denoted by gamma(a)(D), is defined as the minimum cardinality of an absorbant of D. The generalized de Bruijn digraph G(B)(n,d) is a digraph with the vertex set V(G(B)(n, d)) = {0, 1, 2, ..., n - 1} and the arc set A(G(B)(n, d)) = {(x, y)vertical bar y equivalent to dx + i (mod n),0 <= i < d}. In this paper, we determine gamma(a)(G(B)(n, d)) for all d <= n <= 4d.