کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649085 | 1632448 | 2007 | 18 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 307, Issues 3–5, 6 February 2007, Pages 615–632