One topic of some interest has been to determine the dominating numbers of grid graphs (meshes), which are just graphs of the form P(n) x P(m), where P(n) is the path of n vertices. Marilynn Livingston and I showed that for any graph G, the domination number of the family G x P(n) has a closed formula (as a function of n), which can be found computationally. This appears in
M.L. Livingston and Q.F. Stout, ``Constant time computation of minimum dominating sets'', Congresses Numerantium 105 (1994), pp. 116-128.This proof used a combination of dynamic programming and properties of minimal weight paths in graphs (the relevant graphs being state graphs that arise in the dynamic programming). Further, it extends to a great many other properties beyond simple domination, including problems involving covers, independence, packing, mispacking, coding, tilings, etc. It can also be extended to counting problems such as dimer problems, where one is counting the number of maximal packings. For some problems, such as determining if perfect dominating sets exist, the computations are somewhat easier because the relevant state space is smaller and the question is merely whether a path of specified length exists.
Abstract Paper.ps (Postscript) Paper.pdf (PDF)
However, there are several conjectures, open questions, and generalizations not yet finished. A few of these are
Even the special case where G is a single point and d=2, is unknown, as our approach only works for d=1 (though G can be arbitrary). I further believe that this is true for a very wide range of properties, not just domination.
Our approach cannot be proven to work here, because there is no constraint on the values that may be used. If one could restrict them to a finite set, then the approach would apply. We know of a few other forms of domination which have similar difficulties, though it seems that most of the forms of domination which occur in practice are amenable to our approach.
For example, our results can be extended from paths to cycles and complete t-ary trees. Recently we realized that one can prove that there is a closed form for some simple doubly-indexed families, such as rooted trees with m subtrees, each of which is P(n), and this approach can be extended to various other construction techniques.
Copyright © 2004-2016 Quentin F. Stout |