Approximations of the Domination Number of a Graph Glenn G. Chappell John Gimbel 7 Department of Computer Science Department of Mathematics and Statistics 1 0 University of Alaska University of Alaska 2 Fairbanks, AK 99775-6670 Fairbanks, AK 99775-6660 n a [email protected] [email protected] J 1 Chris Hartman 2 Department of Computer Science ] O University of Alaska C Fairbanks, AK 99775-6670 . h [email protected] t a m January 17, 2017 [ 1 v 1 2010 Mathematics Subject Classification. 05C69 (primary), 05C80 (secondary). 6 Key words and phrases. domination, fractional domination, greedy domination, random graphs. 9 5 0 . Abstract 1 0 Given a graph G, the domination number γ(G) of G is the minimum order of 7 a set S of vertices such that each vertex not in S is adjacent to some vertex in 1 : S. Equivalently, label the vertices from {0,1} so that the sum over each closed v neighborhood is at least one; the minimum value of the sum of all labels, with this i X restriction, is the domination number. The fractional domination number γ (G) is f r defined in the same way, except that the vertex labels are chosen from [0,1]. Given a anorderingofthevertexsetofG, letγ (G)betheapproximationofthedomination g number by the standard greedy algorithm. Computing the domination number is NP-complete; however, we can bound γ by these two more easily computed param- eters: γ (G) ≤ γ(G) ≤ γ (G). f g How good are these approximations? Using techniques from the theory of hyper- graphs, one can show that, for every graph G of order n, γ (G) g = O(logn). γ (G) f 1 On the other hand, we provide examples of graphs for which γ/γ = Θ(logn) and f graphs for which γ /γ = Θ(logn). Lastly, we use our examples to compare two g bounds on γ . g Graphs will be finite, simple, and undirected. For a graph G, we denote by δ(G) and ∆(G) the minimum and maximum degree of G, respectively. We use N[v] to denote the closed neighborhood of a vertex v. The closed neighborhood of a sequence of vertices, e.g., N[v ,v ,...,v ], is the union of the closed neighborhoods of the vertices in the 1 2 k sequence. We say that vertex v dominates vertex u if u lies in the closed neighborhood of v. See Haynes, Hedetniemi, & Slater [8] for definitions of graph-theoretic terms and an introduction to domination in graphs. If we assign weights to the vertices of a graph, then the total weight of a set of vertices is the sum of the weights of the vertices in the set. We may consider a dominating set as a 0,1-weighting of the vertex set so that the total weight of each closed neighborhood is at least one. Relaxing the requirement that the weights be integers, we obtain a fractional version of the domination number. Suppose we assign weight f(v) ∈ [0,1] to each vertex v. The function f: V(G) → [0,1] is a fractional domination if for each vertex v, (cid:88) f(u) ≥ 1. u∈N[v] The fractional domination number γ (G) of G is the minimum total weight of the vertex f set, taken over all fractional dominations of G. A useful bound is the following, which was discovered independently by Grinstead & Slater [7, Theorem 1] and by Domke, Hedetniemi, & Laskar [5, Observation 3] (Observa- tion 3 in the latter paper is slightly misstated, with the inequalities in the wrong direction, but the proof is correct). Lemma 1. For a graph G of order n, n n ≤ γ (G) ≤ . (cid:3) f 1+∆(G) 1+δ(G) Throughout this paper, we will implicitly assume an ordering on the vertex set of a graph. Given such an ordering, we can approximate the domination number us- ing a greedy algorithm, as follows. Iteratively select vertices x ,x ,...,x so that, 1 2 m for each k = 1,2,...,m, vertex x is chosen so that it dominates as many vertices of k V(G) − N[x ,x ,...,x ] (that is, not-yet-dominated vertices) as possible. Resolve ties 1 2 k−1 by choosing x as early as possible in the ordering on V(G). Stop the iterative process k when every vertex is dominated by one of the x ’s. We refer to x ,x ,...,x as the k 1 2 m greedy dominating sequence. The greedy domination number γ (G) = m is the number of g vertices in this sequence. Determining the domination number of a general graph is known to be NP-complete (see Garey & Johnson [6]); it is natural to seek more easily computed approximations. The values of γ and γ can be determined in polynomial time. Further, the fact that γ f g lies in the interval [γ ,γ ] follows easily from definitions. f g 2 Observation 2. For every graph G, γ (G) ≤ γ(G) ≤ γ (G). (cid:3) f g We study the relationships of these three parameters further. Techniques from the theory of hypergraphs can be used to show that the ratio γ (G)/γ (G) is O(log∆), and thus O(logn), where n is the order of G; see Theorem 4, g f below. Thus γ(G) must lie within a relatively small interval. We produce examples show- ing that, asymptotically, we can do no better. We show that γ(G)/γ (G) can be Θ(logn), f and then we show that γ (G)/γ(G) can be Θ(logn). g Since γ is a useful upper bound on γ, it is worthwhile to consider upper bounds on g γ . One such bound follows immediately from the above discussion: g γ (G) ≤ cγ (G)logn, g f for some constant c, where n is the order of G. Another class of bounds are those in which γ is bounded above by a constant multiple of (nlogδ)/δ. The first of these was found g by Alon & Spencer [1] (see their Theorem 2.2 and the remarks following it). A slightly improved bound was given by Clark, Shekhtman, Suen, & Fisher [4, Theorem 2]; we state this below. Theorem 3 (Clark, Shekhtman, Suen, & Fisher [4]). For every graph G of order n, (cid:34) (cid:35) δ+1 (cid:89) iδ γ (G) ≤ n 1− , g iδ +1 i=1 where δ = δ(G). (cid:3) (cid:0) (cid:1) We note that the right side of the above inequality is Θ [nlogδ]/δ . At the conclusion of this paper, we will compare these two bounds on γ , using examples to show that g sometimes one is tighter, and sometimes the other is. In the following result, we will use a concept dual to fractional domination. A function f: V(G) → [0,1] is a fractional packing if for each vertex v, (cid:88) f(u) ≤ 1. u∈N[v] Note that the maximum total weight of V(G), taken over all fractional packings, and the minimum total weight of V(G), taken over all fractional dominations, are described by dual linear programs (see Haynes, Hedetniemi, & Slater [8, Chapter 4] or Domke, Hedetniemi, & Laskar [5, Section 3]). Thus, by the principle of strong duality, given a fractional packing on a graph G, the total weight of the vertex set is at most γ (G). f Wenowproveanupperboundonγ (G)/γ (G). Thisisaspecialcaseofamoregeneral g f result on vertex covers of hypergraphs and is similar to a bound found by Johnson [9, Theorem 4] and by Lova´sz [10, Corollary 2] (see also Schrijver [13, Theorem 77.2]). 3 Theorem 4. For every graph G, γ (G) g (cid:2) (cid:3) ≤ 1+ln 1+∆(G) . γ (G) f Proof. Set m = γ (G). Let x ,x ,...,x be the greedy dominating sequence. For each g 1 2 m vertexv ofG,letg(v)bethefirstvertexinthegreedydominatingsequencethatdominates v. Let F(v) be the set of all vertices of G that are first dominated by g(v); that is, F(v) = N[x ] − N[x ,x ,...,x ], where x = g(v). Let w(v) = 1 . So w(v) is the k 1 2 k−1 k |F(v)| reciprocal of the number of vertices that are dominated in the same step of the greedy (cid:80) (cid:80) algorithm as v. Note that w(u) = 1, and thus w(v) = m. u∈F(v) v∈V(G) Our proof is based on that of Schrijver [13, Theorem 77.2], and proceeds as follows. We assign weight w(v) to each vertex v. We find upper bounds on the weights of ver- tices lying in a closed neighborhood, and conclude that, if each vertex v is given weight (cid:0) (cid:2) (cid:3)(cid:1) w(v)/ 1+ln 1+∆(G) , then the result is a fractional packing. Applying linear pro- gramming duality, we then obtain a lower bound on γ (G), from which our result follows. f Let v be a vertex of G. We list the elements of N[v] in the order in which they were dominated in the greedy algorithm. Letting p = 1 + deg(v), we represent N[v] as {u ,u ,...,u }, where, if g(u ) comes before g(u ) in the greedy dominating sequence, 1 2 p i j then i < j. We claim that w(u ) ≤ 1 for each u . Suppose for a contradiction that |F(u )| < i p+1−i i i (cid:12) (cid:12) p + 1 − i, for some u . Then |F(u )| < (cid:12){u ,u ,...,u }(cid:12), and so replacing g(u ) by i i i i+1 p i v in the greedy dominating sequence would increase the number of vertices dominated at this step in the greedy algorithm. However, this contradicts the definition of greedy dominating sequence, and so |F(u )| ≥ p+1−i. Thus, i 1 1 w(u ) = ≤ , i |F(u )| p+1−i i as claimed. Hence, for each vertex v we have p p (cid:88) (cid:88) 1 (cid:88) 1 (cid:2) (cid:3) w(u) ≤ = ≤ 1+lnp ≤ 1+ln 1+∆(G) . p+1−i i u∈N[v] i=1 i=1 (cid:2) (cid:3) Dividing by 1+ln 1+∆(G) , we obtain (cid:88) w(u) ≤ 1, (cid:2) (cid:3) 1+ln 1+∆(G) u∈N[v] (cid:0) (cid:2) (cid:3)(cid:1) and so assigning weight w(v)/ 1+ln 1+∆(G) to each vertex v, results in a fractional packing. Therefore, as noted before the statement of the theorem, the sum of all vertex weights is bounded above by γ (G). That is, f (cid:88) w(v) ≤ γ (G). (cid:2) (cid:3) f 1+ln 1+∆(G) v∈V(G) 4 (cid:2) (cid:3) Multiplying by 1+ln 1+∆(G) , we obtain (cid:88) (cid:0) (cid:2) (cid:3)(cid:1) γ (G) = m = w(v) ≤ 1+ln 1+∆(G) γ (G). g f v∈V(G) Dividing by γ (G) yields our result. (cid:3) f Hence the following. Corollary 5. For any graph G of order n with maximum degree ∆ ≥ 2 γ(G) ≤ c ln(∆)γ (G) 1 f and γ(G) ≤ c ln(n)γ (G), 2 f where c and c are appropriately chosen constants. (cid:3) 1 2 The preceding theorem and corollary place restrictions on the value of γ. We now show that these restrictions are asymptotically best possible up to a constant factor. We begin with a construction of a family of graphs in which γ lies near the high end of the interval [γ ,γ ]. Later, we will obtain better results using random graphs. f g Example 6. Given a positive integer t, we construct a graph J of order n = (2t)2t−1 t such that γ (J ) = e+o(1) = Θ(1) f t and (cid:18) (cid:19) logn γ(J ) = 2t = Θ . t loglogn Let t be a positive integer. Set d = 2t − 1 and n = (2t)d. Let G be the graph K − tK , that is, K with a perfect matching removed. Let J be the graph whose 2t 2 2t t vertices are d-tuples of the form (x ,x ,...,x ) where each x is a vertex in G. Let 1 2 d i vertices (x ,x ,...,x ) and (y ,y ,...,y ) be adjacent in J if for each i, the vertices x 1 2 d 1 2 d t i and y are equal or adjacent in G. (The way in which J is constructed from G is often i t called the “strong [direct] product”.) We note that J has order n. t We show that J has the required properties. For each vertex v of G, denote by v the t unique vertex in G that is not adjacent to v. Note that J is regular of degree (2t−1)d −1. By Lemma 1, t n (d+1)d γ (J ) = = = e+o(1). f t (2t−1)d dd (cid:8) (cid:12) (cid:9) Let S be a set of d vertices of J . We write S = (xi,xi,...,xi) (cid:12) i = 1,2,...,d . t 1 2 d (cid:16) (cid:17) Let u = x1,x2,...,xd . Then u is not dominated by any vertex in S, so S is not a 1 2 d dominating set. Hence, the domination number of J is at least d+1. Now let A be the t set of all vertices in J of the form (v,v,v,...,v) where v is a vertex in G. Since there are t d+1suchvertices, butonlydcoordinates, everyvertexofJ mustbedominatedbyatleast t one vertex of A. Thus, A is a dominating set of size d+1, and so γ(J) = d+1 = 2t. (cid:3) 5 For the graph J of Example 6, γ/γ = Θ(logn/loglogn). Thus we have constructed t f an infinite family of graphs for which the ratio γ/γ is unbounded. However, the ratio is f not as high as we would like. Using random graphs, we can produce better examples, for which γ/γ is, with high probability, Θ(logn). f For each natural number n, let R be a random graph on n labeled vertices with edge n probability 1/2. Given a graphical property P we say that R almost surely (a.s.) has P n if the probability that R has P goes to one as n approaches infinity. See Palmer [12] for n an introduction to random graphs. ItisknownthatthedominationnumberofR isalmostsurelyΘ(logn)(seeNikoletseas n & Spirakis [11, Lemmas 1 & 2]). In fact, much stronger results are known. Weber [14, Theorem 2] showed that γ(R ) is a.s. equal to one of two values given by explicit formulae. n For our purposes, it suffices that γ(R ) is a.s. Θ(logn). On the other hand, γ (R ) is a.s. n f n Θ(1). We give a short proof of these facts below. Theorem 7. Almost surely, γ (R ) = 2+o(1) f n and γ(R ) = Θ(logn). n Proof. It is known that the degrees of all vertices in R tend to concentrate tightly around n n/2. In particular, a.s. n n (cid:2) (cid:3) (cid:2) (cid:3) 1−o(1) ≤ δ(R ) ≤ ∆(R ) ≤ 1+o(1) . n n 2 2 This follows from a Chernoff bound [3, Theorem 1]; for a proof, see Palmer [12, Theo- rem 5.1.4]. Applying Lemma 1, we conclude that a.s. γ (R ) = 2+o(1). f n Since γ (R ) is a.s. Θ(1), by Corollary 5 we see that γ(R ) is a.s. O(logn). It remains f n n (cid:4) (cid:5) to show that γ(R ) is a.s. Ω(logn). Fix ε with 0 < ε < 1. Set p = (1−ε)log n . We n 2 show that a.s. γ(R ) > p, which will complete our proof. n Our argument is similar to that given by Nikoletseas & Spirakis [11, Lemma 1]. Let S be a subset of V(G) with order p. If v is a vertex not in S then the probability that S dominates v is 1−(cid:0)1(cid:1)p. Hence, the probability that S dominates R is (cid:2)1−(cid:0)1(cid:1)p(cid:3)n−p. 2 n 2 Let E be the expected number of p-sets that dominate R . Then, n (cid:18)n(cid:19)(cid:20) (cid:18)1(cid:19)p(cid:21)n−p (cid:104) (cid:105)n−p E = 1− ≤ np e−(1/2)p p 2 ≤ npe−(1/n1−ε)(n−p) since 2p ≤ n1−ε = epln(n)−(n/n1−ε)ep/n1−ε ≤ cepln(n)−nε, for some constant c. But the last expression goes to zero as n approaches infinity. Hence, R a.s. has no dominating p-set. This leads to the desired result. (cid:3) n 6 When the random graph R almost surely has some property, we may conclude that, n for each sufficiently large n, there exists a graph of order n having the property. Hence, we obtain the following. Corollary 8. There exist graphs G , for infinitely many integers n, so that each G has n n order n, and γ(G ) n = Θ(logn). (cid:3) γ (G ) f n Thus, the bounds in Corollary 5 are asymptotically best possible. We have proven this using probabilistic methods. The best explicit construction we have been able to find is that of the graphs J from Example 6, for which the ratio γ/γ is smaller: t f Θ(logn/loglogn). We ask whether an explicit construction can be found for the larger ratio. Problem 9. Find an explicit construction of graphs G , for infinitely many integers n, n so that each G has order n, and n γ(G ) n = Θ(logn). (cid:3) γ (G ) f n We have seen that γ /γ is O(logn), and that the ratio γ/γ may be Θ(logn). In g f f our next example the ratio γ /γ is Θ(logn). Thus, γ is near the low end of the interval g [γ ,γ ], and the greedy algorithm approximates the domination number relatively poorly. f g Example 10. Given an integer t ≥ 4, we construct a graph H of order n = 2t+2 such t that γ (H ) = γ(H ) = 4 f t t and γ (H ) = t = Θ(logn). g t Lett ≥ 4beanaturalnumber. Letu ,u ,u ,u beverticesandsetS = {u ,u ,u ,u }. 1 2 3 4 1 2 3 4 To construct H , begin with the union of S and t disjoint cliques: t (cid:2) (cid:3) S ∪ K ∪K ∪K ∪···∪K . 4 8 16 2·2t Add additional edges so that each vertex of S is adjacent to one quarter of the vertices in each clique, and no two vertices of S have any common neighbors. Let H be the resulting t graph. We note that the order of H is t (cid:2) (cid:3) 4+4 1+2+4+···+2t−1 = 2t+2. Given a fractional domination of H , the total weight of the vertices in each N[u ] t i is at least 1. Since the sets N[u ], N[u ], N[u ], N[u ] are pairwise disjoint, we have 1 2 3 4 γ (H ) ≥ 4. On the other hand, S dominates H , so γ(H ) ≤ 4. Thus, f t t t 4 ≤ γ (H ) ≤ γ(H ) ≤ 4, f t t 7 and we have γ (H ) = γ(H ) = 4. f t t If we approximate γ(H ) with the greedy algorithm, then we will never choose any t vertex in S. The greedy dominating sequence will contain one vertex from each of the cliques used to construct H . Since t ≥ 4 the first four such vertices chosen will dominate t the four vertices in S, and so γ (H ) = t. (cid:3) g t Letting n = 2t+2, and letting G be H from the above example, we obtain the follow- n t ing. Corollary 11. There exist graphs G , for infinitely many integers n, so that each G has n n order n, and γ (G ) g n = Θ(logn). (cid:3) γ(G ) n We now consider upper bounds on γ . By Theorem 4 we have, for a graph G of order g n, γ (G) ≤ c γ (G)logn, (1) g 1 f for some constant c . And by Theorem 3, we have 1 nlogδ(G) γ (G) ≤ c , (2) g 2 δ(G) for some constant c . 2 Consider these bounds for the graph H from Example 10. We have γ (H ) = 4, and t f t clearlyδ(H ) = 4. Thus, lettingnbetheorderofH , theright-handsideof(1)isΘ(logn), t t while the right-hand side of (2) is Θ(n), making (1) by far the tighter bound. On the other hand, let t be a positive integer, and let G be a t-clique with a pendant vertex joined to each clique vertex (a “hairy clique”). Letting n be the order of G, we have γ (G) = t = n/2, and δ(G) = 1. Thus, the right-hand side of (1) is Θ(nlogn), while f the right-hand side of (2) is Θ(n), making (2) the tighter bound. References [1] N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, New York, 1992. [2] B. Bollob´as and P. Erd˝os, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1976), no. 3, 419–427. [3] H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), no. 4, 493–507. [4] W.E. Clark, B. Shekhtman, S. Suen, and D.C. Fisher, Upper bounds for the domi- nation number of a graph, in Proceedings of the Twenty-ninth Southeastern Interna- tional Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1998), Congr. Numer. 132 (1998), 99–123. 8 [5] G.S. Domke, S.T. Hedetniemi, and R.C. Laskar, Fractional packings, coverings, and irredundance in graphs, in Proceedings of the Nineteenth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1988), Congr. Numer. 66 (1988), 227–238. [6] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. [7] D.L. Grinstead and P.J. Slater, Fractional domination and fractional packing in graphs, in Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congr. Numer. 71 (1990), 153–172. [8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998. [9] D.S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. System Sci. 9 (1974), 256–278. [10] L. Lova´sz, On the ratio of optimal integral and fractional covers, Discrete Math. 13 (1975), no. 4, 383–390. [11] S.E. Nikoletseas and P.G. Spirakis, Near-optimal dominating sets in dense random graphs in polynomial expected time, in Graph-Theoretic Concepts in Computer Sci- ence, J. van Leeuwen, ed., Lecture Notes in Computer Science 790, Springer, Berlin, 1994, 1–10. [12] E.M.Palmer,Graphical Evolution: An Introduction to the Theory of Random Graphs, Wiley, Chichester, 1985. [13] A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Vol. C: Disjoint Paths, Hypergraphs, Springer-Verlag, Berlin, 2003. [14] K. Weber, Domination number for almost every graph, Rostock. Math. Kolloq. 16 (1981), 31–43. 9