On efficient absorbant conjecture in generalized De Bruijn digraphs
Kuo-Hua Wu, Yue-Li Wang, Ton Kloks · International Journal of Computer Mathematics · 2016
An absorbant of a digraph D is a set S⊆V(D) such that, for every v∈V(D)∖S, there exists an arc (v,u) with u∈S. An absorbant S is efficient if no two vertices in S have a common in-neighbour and the subdigraph induced by S has no arc. The efficient absorbant conjecture in generalized De Bruijn digraphs is as follows: There exists an efficient absorbant in generalized De Bruijn digraph GB(n,d) with n=c(d+1) if and only if c is a multiple of gcd(n,d−1). In this paper, we show that the sufficient condition of the efficient absorbant conjecture in generalized De Bruijn digraphs is affirmative.