compiled by
Steve Hedetniemi
Department of Computer Science
Clemson University
Clemson, SC 29634-1906
Approximately 1,100 papers have been published on the general subject of domination in graphs. However, to the best of my knowledge, no one has published a paper containing an algorithm for computing the domination number of an arbitrary graph G.
The answer to this question is always 'yes' [ ]. The question here is can such a dominating clique be found in polynomial time?
In the independence game, two players alternate taking turns placing a Queen on the board. The rule is that at all times the set of Queens placed on the board must be an independent (non-attacking) set. The first player who cannot place an additional Queen without being attacked by an existing Queen loses the game.
Weakley points out that on odd boards Q(2n+1), Player 1 always wins, by first placing a Queen in the center square and then playing 'opposite' to Player 2's moves. Harary says that on the standard 8 x 8 board, a computer search has shown that Player 1 can always win, but the strategy is 'messy'.
Note the full generality of the independence game. One can play it with Bishops and Rooks (for which the solution is simple), Kings, Knights and Crosses (for which I know of no solution).
One can also play the 'irredundance game', in which the set of pieces played must always be an irredundant set, and the 'domination game', in which each piece played must dominate a square not dominated by any other piece.
What is the minimum number of edges that can be added to an arbitrary tree T so that the resulting domination number is less than that for T? This is called the reinforcement number of T, and is denoted r(T). Can you construct a linear algorithm for determining r(T) for an arbitrary tree T? [J. Kok and C.M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79(1990) 225-231].
Note that it has been shown that every graph G has an ODD NEIGHBORHOOD COVER, although not every graph has an EVEN NEIGHBORHOOD COVER. Dawes has constructed a polynomial algorithm for deciding if an arbitrary tree T has an ODD NEIGHBORHOOD COVER of size <= K [19XX]. [R.W. Dawes, Neighborhood covers for trees. Tech. Rept. ISSN-0836-0227, Dept. Computing and Information Science, Queen's Univ., 1990].
A positive, real-valued function f: V --> (0,1] on the vertices of a graph G = (V,E) is a positive dominating function if for every vertex v in V, f(N[v]) >= 1. A positive dominating function f is minimal if for every vertex u there exists a vertex w in N[u] for which f(N[w]) = 1. [E.J. Cockayne, G. Fricke, S.T. Hedetniemi and C.M. Mynhardt, Properties of minimal dominating functions of graphs, Ars Combin. 41 (1995), 107-115].
Here g (G) denotes the domination number of G. Jacobson and Kinch have proved that: g (GXH) >= P2(G) g (H), where P2(G) denotes the 2-packing number of G (i.e. the maximum number of vertices in a set S such that for every vertex v in V, |N[v] intersect S| <= 1).
Here g f(G) denotes the fractional domination number of G, i.e. the minimum weight of a dominating function f on G, i.e. a function f: V --> [0,1] such that for every vertex v in V, f(N[v]) >= 1. [cf. B.L. Hartnell and D.F. Rall, Domination in cartesian products: Vizing's conjecture. In T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Editors, Domination in Graphs: Advanced Topics, Chapter 7. Marcel Dekker, Inc., 1998]
The strong matching number of a graph G is the maximum number of edges in a set M such that the subgraph induced by V(M), the set of vertices contained in the edges in M, consists of disjoint copies of K2. Laskar and Golumbic have constructed a linear algorithm for computing the strong matching number of any tree and any circular arc graph. They also showed that this problem is NP-complete for arbitrary graphs. I know of no other strong matching algorithm. [K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97-102] [M.C. Golumbic and R.C. Laskar, Irredundancy in circular arc graphs, Discrete Appl. Math. 44 (1993) 79-89]
A vertex set D is an n-dominating set if all vertices NOT in D are adjacent to at least n vertices in D. Let g n(G) be the order of the smallest n-dominating set in G. Show that, for any positive integer n, there exists a positive integer M such that g n(G) < g M(G), for all graphs G with minimum degree greater than or equal to n. Let f(n) be the smallest such integer M. What is the function f(n)? Does it even exist?
Originally Fink and Jacobson conjectured that f(n) = 2n+1. In a paper of Rall, Peters and Jacobson it is shown that f(n) > (n2)/ 4, if the function exists. Fink and Jacobson have shown that g 1(G) < g 3(G) for all graphs with min degree >= 1. And recently Chen and Jacobson have shown that f(2) = 5, i.e. g 2(G) < g 5(G), for all graphs with min degree 2, and this can't be improved.
A set S of vertices is irredundant if for every vertex u in V, the set N[u] - N[S-u] is not empty. The irredundance number of a graph ir(G) equals the minimum cardinality of a maximal irredundant set in G. Bern, Lawler and Wang [1987] have constructed a non-trivial, linear algorithm for computing the irredundance number of an arbitrary tree T. This algorithm is defined in terms of a 19x19 table of entries. There is also a linear algorithm for computing the irredundance number of an arbitrary, weighted interval graph. I know of no other algorithm for computing the irredundance number of any other family of graphs; can you construct one? The NP-completeness of IRREDUNDANT SET, even for bipartite graphs, was constructed by Pfaff in 1984 [cf. J. Pfaff, S.T. Hedetniemi and R. Laskar, Irredundance in graphs: a survey, Congr. Numer. 48 (1985), 183-193] [M.W. Bern, E.L. Lawler and A.L. Wong, Linear-time computation of optimal subgraphs of decomposable graphs, J. Algorithms 8(2)(1987) 216-235].
A set of vertices S is total irredundant if for every vertex v in S , N[v] - N[S-v] is not empty. If S is a total irredundant set then every vertex u in V satisfies at least one of the following two conditions: (i) u is not adjacent to any vertex in S, or (ii) u has a private neighbor with respect to S, i.e. u is adjacent to at least one vertex, say w in V-S and w is not adjacent to any vertex in S. Consider the class of all maximal total irredundant sets. The upper total irredundance number, denoted IRt(G), equals the maximum cardinality of a maximal total irredundant set in G, and the lower total irredundance number, denoted irt(G), equals the minimum cardinality of a maximal total irredundant set in G. A linear algorithm has been constructed for determining IRt(T) for an arbitrary tree T [S.M. Hedetniemi, S.T. Hedetniemi and Jacobs]. Can you construct a linear algorithm for determining irt(T) for an arbitrary tree T? The NP-completeness of the decision problem for IRt(G) has been established for arbitrary graphs, but not for bipartite graphs. The NP-completeness problem for irt(G) has not been established. [S.M. Hedetniemi, S.T. Hedetniemi and D.P. Jacobs, Total irredundance in graphs: theory and algorithms, Ars. Combin. 35A (1993) 136-148].
p
A function g: V --> [0,1], which assigns to each vertex v in a graph G = (V,E) a rational number in the unit interval [0,1], is said to be an irredundant function if for every vertex v with g(v) > 0 there exists a vertex w in N[v] with g(N[w]) = 1. Consider the class of maximal irredundant functions and for each such function consider the value g(V), which is the sum of all values g(v) over all v in V. The value irf(G) is the infimum of this class of functions and is called the lower fractional irredundance number of G. No one has yet constructed ANY algorithm for computing the value of irf(G) for any nontrivial class of graphs, nor determined whether the corresponding decision problem is NP-complete. Can you construct an algorithm for determining the value irf(T) for an arbitrary tree T? or even an arbitrary path P? Gerd Fricke [1993] has shown that for the path P7, irf(P7)=2 < ir(P7)=3.
A set of vertices S is externally redundant [definition due to A. McRae] if for every vertex u in V-S, at least one of the following two conditions holds: (i) vertex u has no private neighbor with respect to the set S union {u}; (ii) there exists a vertex w in S which has a private neighbor with respect to S, but has no private neighbor with respect to set S union {u}.
Note that this is an example of a property of a set of vertices for which a set S can be 1-minimal externally redundant, but not minimal externally redundant.
A dominating function is a function f: V --> [0,1] such that for every vertex v in V, f(N[v]) >= 1. Erdös, upon hearing this problem, speculated that such a function cannot be defined.
This problem is obviously NP-complete, since the decision problem associated with the K-domination number is NP-complete. But the real question here is this. It can be proved that the fractional domination number of any graph G equals the minimum value of the ratio of the K-domination number divided by K, over all positive integers K. For a given graph G consider the minimum value of K for which this equality holds. How large can this minimum value be?
Definitions. The K-domination number of a graph G equals the minimum value f(V) over all functions f: V --> {0,1,2,...,K} such that for every vertex v in V, f(N[v]) >= K. The fractional domination number equals the minimum value f(V) over all dominating functions f: V --> [0,1], i.e. for every vertex v in V, f(N[v]) >= 1.
(cf. FRACTIONAL DOMINATION) A K-dominating function f is minimalI/cite> if for every vertex v with f(v) > 0, there exists a vertex w in N[v] such that f(N[w]) = K. The upper K-domination number of G is the maximum value f(V) of a minimal K-dominating function on G. The question here is really this: is the K-domination number of a graph G always <= the (K+1)-domination number of G?
It appears that for many standard classes of graphs, the answer to this question is 'yes'.