compiled by

Steve Hedetniemi

Department of Computer Science

Clemson University

Clemson, SC 29634-1906

- DOMINATION NUMBER
- INSTANCE: A graph G = (V,E), a positive integer K.
- QUESTION: Does G have a dominating set of size <= K?

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.

- DOMINATING CLIQUE [19XX]
- INSTANCE: A graph G = (V,E) which is P
_{5}and C_{5}free. - QUESTION: Does G have a dominating clique?

The answer to this question is always 'yes' [ ]. The question here is can such a dominating clique be found in polynomial time?

- INSTANCE: A graph G = (V,E) which is P
- APPROXIMATE DOMINATING SET [McRae, 1993]
- INSTANCE: A graph G = (V,E), a positive constant c.
- QUESTION: Does there exist a polynomial algorithm for finding a dominating set in G whose size is within a factor c of the domination number of G?

- QUEEN'S INDEPENDENCE GAME [Harary, 199X]
- INSTANCE: An n x n chessboard, Q
_{n}. - QUESTION: Does Player 1 have a winning strategy in the
Queen's Independence Game on Q
_{n}?

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.

- INSTANCE: An n x n chessboard, Q
- REINFORCEMENT NUMBER [Mynhardt, circa 1990]
- INSTANCE: A tree T = (V,E), a positive integer K.
- QUESTION: Does T have a reinforcing set of size <= K?

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].

- EVEN NEIGHBORHOOD COVER [Dawes, 19XX]
- INSTANCE: A tree T = (V,E), and a positive integer K.
- QUESTION: Is there a non-empty collection C' of closed neighborhoods N[v] of T, with |C'| <= K, such that each vertex v in V is in an even number (possibly zero) of neighborhoods of C'?

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].

- POSITIVE MINIMAL DOMINATING FUNCTION [Cockayne, Fricke,
Hedetniemi and Mynhardt, 1995]
- INSTANCE: A tree T = (V,E) and a positive integer K.
- QUESTION: Does T have a positive minimal dominating function f: V --> (0,1], whose weight,|f(V)|, is <= K?

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].

- VIZING'S CONJECTURE [Vizing, 1963]
- INSTANCE: Graphs G and H.
- QUESTION: Is g(GXH) >= g (G)g(H)?

Here g (G) denotes the domination number of G. Jacobson and Kinch have proved that: g (GXH) >= P

_{2}(G) g (H), where P_{2}(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).- QUESTION1: is g (GXH) >= ir(G)g(H)?
- QUESTION2: is g (GXH) >= ir(G)ir(H)?
- QUESTION3: is g (GXH) >=
g
_{f}(G)g(H) - QUESTION4: is g f(GXH) >=
g
_{f}(G)g_{f}(H)? - QUESTION5: is g (HXH) >= g (H)g(H)?

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] - STRONG MATCHING NUMBER [Cameron, 1989]
- INSTANCE: A graph G = (V,E), a positive integer K.
- QUESTION: Does G have a strong matching set of vertices of size > =K?

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]

- N-DOMINATING SET [Jacobson, 1983]
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) > (n

^{2})/ 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. - IRREDUNDANT SET [Cockayne, Hedetniemi and Miller,
1978]
- INSTANCE: A graph G = (V,E), a positive integer K.
- QUESTION: Does G have a maximal irredundant set of size <= K?

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].

- TOTAL IRREDUNDANCE NUMBER [S.M. Hedetniemi, S.T.
Hedetniemi and D.P. Jacobs, 1993]
- INSTANCE: A tree T = (V,E), a positive integer K.
- QUESTION: Does T have a maximal total irredundant set of size <= K?

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 IR

_{t}(G), equals the maximum cardinality of a maximal total irredundant set in G, and the lower total irredundance number, denoted ir_{t}(G), equals the minimum cardinality of a maximal total irredundant set in G. A linear algorithm has been constructed for determining IR_{t}(T) for an arbitrary tree T [S.M. Hedetniemi, S.T. Hedetniemi and Jacobs]. Can you construct a linear algorithm for determining ir_{t}(T) for an arbitrary tree T? The NP-completeness of the decision problem for IR_{t}(G) has been established for arbitrary graphs, but not for bipartite graphs. The NP-completeness problem for ir_{t}(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

- LOWER FRACTIONAL IRREDUNDANCE NUMBER [S.T. Hedetniemi and
R. Laskar, 198X]
- INSTANCE: A tree T = (V,E), a positive integer K.
- QUESTION: Does T have a maximal irredundant function of weight <= K?

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 ir

_{f(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 ir_{f}(T) for an arbitrary tree T? or even an arbitrary path P? Gerd Fricke [1993] has shown that for the path P7, ir_{f}(P_{7})=2 < ir(P_{7})=3. - MINIMAL EXTERNALLY REDUNDANT SET [McRae, 1993]
- INSTANCE: A graph G = (V,E), a set of vertices S.
- QUESTION: Is S a minimal externally redundant set?

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.

- WEAK MAXIMAL IRREDUNDANT SET [Hedetniemi, 1993]
- INSTANCE: A graph G = (V,E), a positive integer K.
- QUESTION: Does G have a maximal irredundant set which does not dominate >= K vertices?

- FRACTIONAL INDEPENDENCE [Hedetniemi and Laskar, 1988]
- INSTANCE: A graph G = (V,E).
- QUESTION: Can you give a definition of a fractional independent function? i.e. a function f: V --> [0,1] which assigns a value in the unit interval [0,1] to each vertex v in V and which satisfies the following two constraints: (i) the characteristic function of any (maximal) independent set in G is a (maximal) independent function; (ii) every maximal independent function is also a minimal dominating function.

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.

- FRACTIONAL DOMINATION [Hedetniemi and Laskar, 1988]
- INSTANCE: A graph G = (V,E), a positive integer K.
- QUESTION: Is the fractional domination number of G equal to the K-domination number of G divided by K?

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.

- UPPER K-DOMINATION NUMBER [Laskar, Domke and Hedetniemi,
1988]
- INSTANCE: A graph G = (V,E), a positive integer K.
- QUESTION: Is the upper K-domination number of G <= the upper (K+1)-domination number of G?

(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?

- DOMINATING PATH [Hedetniemi, 1993]
- INSTANCE: A graph G = (V,E).
- QUESTION: Does G have a dominating path? i.e. a path P such that every vertex v in V is either on the path or is adjacent to at least one vertex on P.

It appears that for many standard classes of graphs, the answer to this question is 'yes'.