Some Open Problems

Some Open Problems and Conjectures

These problems and conjectures concern the determination of properties of families of graphs. For example, one property of a graph is its domination number. For a graph G, a set S of vertices is a dominating set if every vertex of G is in S or adjacent to a member of S. The domination number of G is the minimum size of a dominating set of G. Determining the domination number of a graph is an NP-complete problem, but can often be done for many graphs encountered in practice.

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.
Abstract Paper.ps (Postscript) Paper.pdf (PDF)

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.

However, there are several conjectures, open questions, and generalizations not yet finished. A few of these are

Conjecture: For every graph G and dimension d, the dominating numbers of the d-dimensional family G x P(n₁) x P(n₂) ... x P(n_d) have a closed form.
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.
Question: Is there an interesting formal language L, so that if a property A (such as domination number) can be expressed in L, then there is a closed form for A(G x P(n))?
Question: For every m, is there a closed form for the fractional dominating number of P(m) x P(n)? (In fractional domination, one can put arbitrary nonnegative real values at each vertex, with the constraint that for every vertex v, the sum of the values of v and all of its neighbors must be at least 1. The fractional dominating number is the minimum possible sum, over all vertices, of these values.)
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.
Question: For what other parameterized families F(n) can one prove that the dominating number of G x F(n) has a closed form?
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.

Here is some more information about some of my work in dynamic programming, applied to a variety of problems.