On efficient absorbant conjecture in generalized De Bruijn digraphs

ABSTRACT

An absorbant of a digraph D is a set $S\subseteq V\left(D\right)$ such that, for every $v\in V\left(D\right)\setminus S$, there exists an arc $(v,u)$ with $u\in 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 $G_B(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.

KEYWORDS:

• Absorbant
• efficient absorbant
• dominating set
• efficient dominating set
• generalized DeBruijn digraph

2010 AMS SUBJECT CLASSIFICATION:

• 05C69 2010

Acknowledgments

The authors would like to thank anonymous referees for their careful reading with corrections and useful comments which helped to improve the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.