کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
5128245 1489490 2017 9 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله
Efficient absorbants in generalized de Bruijn digraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Efficient absorbants in generalized de Bruijn digraphs
چکیده انگلیسی

Let D=(V,A) be a digraph with vertex set V and arc set A. An efficient absorbant (respectively, dominating set) of a digraph D=(V,A) is a set S⊆V such that, for every v∈V∖S, there exists exactly one out-neighbor (respectively, in-neighbor) of v in S and there is no arc in the induced digraph of S, where an out-neighbor (respectively, in-neighbor) of v in S is a vertex u with an arc (v,u) (respectively, (u,v)) in A with u∈S. The efficient absorbant conjecture is as follows: there is an efficient absorbant in generalized de Bruijn digraph GB(n,d) if and only if nd+1 is a multiple of gcd(n,d−1), where gcd(x,y) denotes the greatest common divisor of integers x and y. The sufficient condition of this conjecture was proved in DOI:10.1080/00207160.2016.1154949. In this paper, we settle the conjecture. Moreover, we also show that, the subclasses in GB(n,d) having efficient absorbants and efficient dominating sets are equivalent.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 25, August 2017, Pages 77-85
نویسندگان
, , ,