کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649085 1632448 2007 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Critical cyclic patterns related to the domination number of the torus
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Critical cyclic patterns related to the domination number of the torus
چکیده انگلیسی

The concern here is the domination number of the torus, γ(Tm,n)γ(Tm,n). Directly, this paper closes out a significant subset of cases, not only calculating periodic values of γ(Tm,n)γ(Tm,n), but also providing dominating sets with minimal cardinality.The work here builds from a 1994 Livingston and Stout result: For any fixed value of mm, the existence of a closed-form formula in nn, cyclic in nature, is assured. With that expression the value of γ(Tm,n)γ(Tm,n) can be calculated in constant time relative to nn. Unfortunately, given mm as a parameter, algorithms known to produce the closed-form expression in nn run in exponential   time relative to mm. In brief, the related problem has an unknown complexity.The material here pursues the critical cyclic element predicted by the Livingston and Stout material (for any general mm) through the evaluation ofF(m)=limn⟶∞γ(Tm,n)n(this limit is an overall minimum on the average-cost-per-row of domination sets for the torus). Knowledge of this quantity provides explicit, periodic values of nn such that γ(Tm,n)=nF(m)γ(Tm,n)=nF(m). Here, F(m)F(m) is precisely calculated whenever mmod5≠3 or m<13m<13.The nature of a closed-form formula for the two-parameter case has been a matter of some conjecture. With respect to the case when mmod5=3, the best bounds here suggest that such a closed-form expression for γ(Tm,n)γ(Tm,n) would not be cyclic in the usual, simple sense.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 3–5, 6 February 2007, Pages 615–632
نویسندگان
,