The Absorbant Number of Generalized de Bruijn Digraphs

Abstract

Let \(D = (V, A)\) be a digraph with vertex set \(V\) and arc set \(A\). An absorbant of \(D\) is a set \(S \subseteq V\) such that for each \(v \in V \setminus S\), \(O(v) \cap S \neq \emptyset\), 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 vertex set \(V(G_B(n, d)) = \{0, 1, 2, \ldots, n-1\}\) and arc set \(A(G_B(n, d)) = \{(x, y) \mid y = dx + i \, (\text{mod} \, n), 0 \leq i < d\}\). In this paper, we determine \(\gamma_a(G_B(n, d))\) for all \(d \leq n \leq 4d\).