Bounds on weak and strong total domination number in graphs

M.H. Akhbari^a , N. Jafari Rad^b

^aDepartment of Mathematics, Estahban Branch, Islamic Azad University, Estahban, Iran

mhakhbari20@gmail.com, n.jafarirad@gmail.com

A set D of vertices in a graph G = (V, E) is a total dominating set if every vertex of G is adjacent to some vertex in D. A total dominating set D of G is said to be weak if every vertex v ∈ V − D is adjacent to a vertex u ∈ D such that dG(v) ≥ dG(u). The weak total domination number γwt(G) of G is the minimum cardinality of a weak total dominating set of G. A total dominating set D of G is said to be strong if every vertex v ∈ V − D is adjacent to a vertex u ∈ D such that dG(v) ≤ dG(u). The strong total domination number γst(G) of G is the minimum cardinality of a strong total dominating set of G. We present some bounds on weak and strong total domination number of a graph.

Keywords: weak total domination, strong total domination, Nordhaus-Gaddum Mathematics Subject Classification : 05C69

DOI:10.5614/ejgta.2016.4.1.10

1. Introduction

We consider finite, undirected, simple graphs. Let G be a graph, with vertex set V and edge set E. The open neighborhood of a vertex v ∈ V is N(v) = {u ∈ V | uv ∈ E} and the closed neighborhood is N[v] = N(v) ∪ {v}. For a subset S ⊆ V , the open neighborhood is N(S) = ∪v∈SN(v) and the closed neighborhood is N[S] = N(S) ∪ S. By G[S] we denote the subgraph induced by the vertices of S. If v is a vertex of V, then the degree of v denoted by dG(v),

Received: 6 April 2015, Revised 21 March 2016 , Accepted: 27 March 2016.

^bDepartment of Mathematics, Shahrood University of Technology, Shahrood, Iran

is the cardinality of its open neighborhood. By ∆(G) = ∆ and δ(G) = δ we denote the maximum and minimum degree of a graph G, respectively. A star K1,n is a tree of order n + 1 with at least n vertices of degree 1. A tree T is a double star if it contains exactly two vertices that are not leaves. We denote by S(a, b) a double star in which one of the centers has degree a and the other center has degree b. The corona cor(G) of a graph G is a graph obtained from G by attaching a leaf to every vertex of G.

A subset S ⊆ V is a dominating set of G if every vertex in V − S has a neighbor in S and is a total dominating set (td-set) if every vertex in V has a neighbor in S. The domination number γ(G) (respectively, total domination number γt(G)) is the minimum cardinality of a dominating set (respectively, total dominating set) of G. Total domination was introduced by Cockayne, Dawes and Hedetniemi [4]. Note that every graph without isolated vertices has a td-set, since V (G) is such a set. In [14], Sampathkumar and Pushpa Latha have introduced the concept of weak and strong domination in graphs. A subset D ⊆ V is a weak dominating set (wd-set) if every vertex v ∈ V −D is adjacent to a vertex u ∈ D, where dG(v) ≥ dG(u). The subset D is a strong dominating set (sdset) if every vertex v ∈ V − D is adjacent to a vertex u ∈ D, where dG(u) ≥ dG(v). The weak (strong, respectively) domination number γw(G) (γs(G), respectively) is the minimum cardinality of a wd-set (an sd-set, respectively) of G. Strong and weak domination have been studied for example in [5, 6, 9, 10, 12, 13]. For more details on domination in graphs and its variations, see the two books [7, 8].

A large part of extremal graph theory studies the extremal values of graph parameters on families of graphs. Results of Nordhaus-Gaddum type study the extremal values of the sum (or product) of a parameter on a graph and its complement, following the classic paper of Nordhaus and Gaddum [11] solving these problems for the chromatic number on n-vertex graphs.

Chellali et al. [3] have introduced the concept of weak total domination in graphs. A total dominating set D of G is said to be weak if every vertex v ∈ V − D is adjacent to a vertex u ∈ D such that dG(v) ≥ dG(u). The weak total domination number γwt(G) of G is the minimum cardinality of a weak total dominating set of G.

Problem 1.1 (Chellali et al. [3]). (1) Can you bound γwt(G) + γwt(G)? (2) What can you say about strong total domination?

The concept strong total domination can be defined analogously. A total dominating set D of G is said to be strong if every vertex v ∈ V − D is adjacent to a vertex u ∈ D such that dG(v) ≤ dG(u). The strong total domination number γst(G) of G is the minimum cardinality of a strong total dominating set of G. We obtain Nordhause- Gaddum type bounds for weak total domination number as well as for strong total domination number of a graph. We also present sharp upper and lower bounds for the strong total domination number of a tree in terms of order and the number of leaves and support vertices. We abbreviate a weak total dominating set of G as wtd-set, and a strong total dominating set of G as std-set. A wtd-set of minimum cardinality is called a γwt(G)-set, and a std-set of minimum cardinality is called a γst(G)-set.

2. Useful results

In this section we state some useful results that we need for the next. We begin with the following observation of [7].

Observation 2.1. For n ≥ 3, γt(Pn) = γt(Cn) = b n 2 c + d n 4 e − bⁿ 4 c.

Proposition 2.1 (Chellali et al. [3]). For any graph G of order n, minimum degree δ and with no isolated vertices, γwt(G) ≤ n + 1 − δ.

The generalized corona G^∗ of a graph G = (V, E) as the graph that is obtained by attaching one or more leaves to each vertex v ∈ V .

Proposition 2.2 (Chellali et al. [3]). A connected graph G of order n ≥ 2 has γwt(G) = n if and only if G is obtained from a generalized corona of a graph H by adding a set of vertices A (possibly empty) attached to vertices of H so that each vertex of A has degree less than the degree of its neighbors.

As a consequent, we have the following.

Corollary 2.1. If G 6= K² is a graph of order n and γwt(G) = n then G has at least two leaves.

We next state some useful results on the total domination number of a graph.

Theorem 2.1 (Cockayne et al. [4]). If G has n vertices, no isolates, and ∆(G) < n − 1, then γt(G) + γt(G) ≤ n + 2, with equality if and only if G or G = mK2.

Theorem 2.2 (Chellali and Haynes [2]). If T is a nontrivial tree of order n ≥ 3 and with s support vertices, then γt(T) ≤ n+s 2 .

Theorem 2.3 (Chellali and Haynes [1]). If T is a nontrivial tree of order n and with l leaves, then γt(T) ≥ n+2−l 2 .

3. Results

We first present Nordhaus-Gaddum type bounds for the weak total domination number as well as strong total domination number, and then present sharp bounds on the strong total domination number in trees.

3.1. Nordhaus-Gaddum type bounds

We obtain sharp upper and lower bounds for γwt(G) +γwt(G), γwt(G)γwt(G), γst(G) +γst(G) and γst(G)γst(G).

Theorem 3.1. Let G be a graph of order n. If G and G have no isolated vertex then γwt(G) + γwt(G) ≤ 2n. Furthermore, the equality holds if and only if G = G = P4.

Proof. The upper bound is obviously verified, thus we prove the equality part. Assume that γwt(G) + γwt(G) = 2n. Then γwt(G) = γwt(G) = n. Since G and G have no isolated vertex, we have δ(G) ≥ 1, δ(G) ≥ 1, ∆(G) ≤ n − 2, and ∆(G) ≤ n − 2. By Proposition 2.2, G is obtained from a generalized corona of a graph H by adding a set of vertices A (possibly empty) attached to vertices of H so that each vertex of A has degree less than the degree of its neighbors. Thus δ(G) = δ(G) = 1. If |V (H)| = 1 then G has an isolated vertex, and if |V (H)| ≥ 3 then δ(G) ≥ 2,

both of which is a contradiction. Thus |V (H)| = 2. Let V (H) = {a, b}. If a is not adjacent to b then δ(G) ≥ 2, a contradiction. Thus a is adjacent to b. If both a and b are strong support vertices, then δ(G) ≥ 2, a contradiction. Thus we may assume, without loss of generality, that there is precisely one leaf adjacent to b. Then b has no neighbor in A. Consequently, deg(b) = 2. Since A is an independent set, we find that G is a double star with centers a and b. If deg(a) ≥ 2, then G has precisely one leaf, contradicting Corollary 2.1. Thus deg(a) = 2. Consequently G = P4. ✷

Theorem 3.2. Let G and G be graphs of order n with no isolated vertex. Then γwt(G) +γwt(G) = 2n − 1 if and only if G or G is cor(C3), or is obtained from a star K1,³ by subdividing one edge.

Proof. Since G and G have no isolated vertex, we have δ(G) ≥ 1, δ(G) ≥ 1, ∆(G) ≤ n − 2, and ∆(G) ≤ n−2. Without loss of generality we may assume that γwt(G) = n and γwt(G) = n−1. By Proposition 2.2, G is obtained from a generalized corona of a graph H by adding a set of vertices A (possibly empty) attached to vertices of H so that each vertex of A has degree less than the degree of its neighbors. Thus δ(G) = 1. By Proposition 2.1, δ(G) ≤ 2. Thus |V (H)| ≤ 3. Assume that |V (H)| = 3. Let V (H) = {a, b, c}. It is obvious that one of the vertices a, b or c has minimum degree in G. Without loss of generality assume that a is a vertex of minimum degree in G. If b or c is adjacent to at least two leaves of G, then δ(G) ≤ 3, a contradiction. Thus each of b and c is adjacent to precisely one leaf of G. Furthermore, a is adjacent to both b and c in G. If a is a strong support vertex in G, then V (G) − {a1, a2} is a wtds for G, where a¹ and a² are leaves adjacent to a. This contradiction implies that a is adjacent to precisely one leaf. Assume that A 6= ∅. If |A| > 1, then V (G) − A is a wtds for G, a contradiction. Thus |A| = 1. Let A = {a0}. If a⁰ is adjacent to both b and c then V (G) − {b1, c1} is a wtds for G, where b¹ is the leaf adjacent to b, and c¹ is the leaf adjacent to c, a contradiction. Thus we may assume that a⁰ is not adjacent to b. Then V (G) − (A ∪ {b1}) is a wtds for G, where b¹ is the leaf adjacent to b, a contradiction. Thus A = ∅, and G = cor(H). If H = P3, then γwt(G) < n − 1, a contradiction. Thus H = C3, and so G = cor(C3).

We next assume that |V (H)| = 2. Let V (H) = {a, b}. If a is not adjacent to b, then G is a disconnected graph with two components K1,¹ and K1,t for some t ≥ 1. Then it can be easily seen that γwt(G) < n − 1, a contradiction. Thus a is adjacent to b. We may assume without loss of generality that a is a vertex of minimum degree in G. Then b is adjacent to at most two leaves. Suppose that b is adjacent to two leaves. Then V (G)− {a1, b1} is a wtds for G, where a¹ is the leaf adjacent to a, and b¹ is the leaf adjacent to b, a contradiction. Thus b is adjacent to precisely one leaf, and thus deg(b) = 2. If deg(a) = 2 then γwt(G) < n−1, a contradiction. If deg(a) ≥ 4, then V (G) − {a1, a2} is a wtds for G, where a¹ and a² are two leaves adjacent to a, a contradiction. Thus deg(a) = 3. Consequently, G is obtained from a star K1,³ by subdividing one edge. ✷

Theorem 3.3. Let G be a graph of order n. If G and G have no isolated vertex then 5 ≤ γwt(G) + γwt(G) ≤ n + ∆(G) + 2. These bounds are sharp.

Proof. For the upper bound, by Proposition 2.1,

\[\gamma_{wt}(G) + \gamma_{wt}(\overline{G}) \leq n + 1 - \delta(G) + n + 1 - \delta(\overline{G})\] \[= n + 1 - \delta(G) + n + 1 - (n - 1 - \Delta(G))\] \[= n + 1 - \delta(G) + 2 + \Delta(G)\] \[\leq n + \Delta(G) + 2.\]

For the lower bound it is obvious that γwt(G) ≥ 2 and γwt(G) ≥ 2. Assume that γwt(G) = γwt(G) = 2. Let S = {x, y} be a γwt(G)-set, and D = {a, b} be a γwt(G)-set. If a = x then y is not dominated by D is G, a contradiction. Thus a 6= x and thus we may assume that S ∩ D = ∅. Clearly we may assume that a is weakly dominated by x and b is weakly dominated by y. Thus degG(x) ≤ degG(a) and degG(y) ≤ degG(b). Since S is γwt(G)-set, we have

\[\deg_G(a) + \deg_G(b) \ge \deg_G(x) + \deg_G(y) \ge n \tag{1}\]

Since D is a γwt(G)-set we obtain that

\[n \le \deg_{\overline{G}}(a) + \deg_{\overline{G}}(b) = n - 1 - \deg_{G}(a) + n - 1 - \deg_{G}(b). \tag{2}\]

(1) and (2) imply that n ≤ degG(a) + degG(b) ≤ n − 2, a contradiction.

To see the sharpness of the upper bound consider a path P4. To see the sharpness of the lower bound consider a double star S(5, 5) with centers {x, y} and leaves {aⁱ , bⁱ : i = 1, 2, 3, 4}, where {xaⁱ : i = 1, 2, 3, 4} ∪ {ybⁱ : i = 1, 2, 3, 4} ⊆ S(5, 5). Now add the edges a1b2, a1b3, a1b4, a2b1, a2b3, a2b4, a3b1, a3b2, a3b4, a4b1, a4b2, a4b3, a1a2, a3a4, b1b3, and b2b⁴ to obtain a graph G. It is straightforward to see that γwt(G) = 2 and γwt(G) = 3.

Similarly we have the following.

Theorem 3.4. Let G be a graph of order n. If G and G have no isolated vertex then 6 ≤ γwt(G)γwt(G) ≤ n 2 . These bounds are sharp.

Next we obtain sharp upper and lower bounds for γst(G) + γst(G) and γst(G)γst(G). The following are easily verified.

Observation 3.1. (1) Every std-set of a graph G contains all support vertices of G. (2) For any graph G with no isolated vertex, γst(G) ≥ γt(G). Moreover, if G is regular, then γst(G) = γt(G).

Proposition 3.1. For paths and cycles, γst(Pn) = γst(Cn) = γt(Pn) = γt(Cn).

For a graph with no isolated vertices, obviously the strong total domination number is bounded above by its order n. Next we improve this upper bound.

Proposition 3.2. For any graph G of order n, maximum degree ∆ and with no isolated vertices, γst(G) ≤ n + 1 − ∆.

Proof. The result holds if \(\Delta(G)=1\), and thus we assume that \(\Delta(G)\geq 2\). Let v be a vertex of V of maximum degree and w be a vertex of N(v). If \(N(v)-\{w\}\) has no support vertex, then \(S=V-(N(v)-\{w\})\) is a strong total dominating set for G. Therefore, \(\gamma_{st}(G)\leqslant |V-(N(v)-\{w\})|=n+1-\Delta\). Thus assume that \(N(v)-\{w\}\) contains some support vertex. Let T be the set of support vertices of \(N(v)-\{w\}\). For each support vertex \(x\in N(v)-\{w\}\), let \(x^*\) be a leaf adjacent to x. Then \(S_1=((N(v)-\{w\})-T)\cup\{x^*:x\in T\}\) is a strong total dominating set for G, and therefore, \(\gamma_{st}(G)\leqslant n+1-\Delta\). \(\square\)

Proposition 3.3. A connected graph G of order \(n \ge 2\) has \(\gamma_{st}(G) = n\) if and only if \(G = K_2\).

Proof. Let G be a graph with \(\gamma_{st}(G) = n\). By Proposition 3.2, we have \(\Delta = 1\). Thus the result follows. \(\Box\)

Proposition 3.4. If G is a connected graph of order \(n \geq 3\) then \(\gamma_{st}(G) \leq n-1\) with equality if and only if \(G \in \{P_3, C_3\}\).

Proof. The upper bound follows from Proposition 3.3. Moreover, it is obvious that \(\gamma_{st}(P_3) = \gamma_{st}(C_3) = 2 = n-1\). Let G be a connected graph with \(\gamma_{st}(G) = n-1\). By Proposition 3.2, we find that \(\Delta(G) \leq 2\). Since \(n \geq 3\) we have \(\Delta(G) = 2\). Thus G is a path or a cycle. By Observation 2.1 and Proposition 3.1, we obtain that \(n-1 = \lfloor \frac{n}{2} \rfloor + \lceil \frac{n}{4} \rceil - \lfloor \frac{n}{4} \rfloor\) and this implies that n=3. Hence \(G \in \{P_3, C_3\}\).

Observation 3.2. For a graph G, \(\gamma_{st}(G) = 2\) if and only if G is a star or a double star.

Theorem 3.5. Let G be a graph of order n. If G and \(\overline{G}\) have no isolated vertex then \(4 \leq \gamma_{st}(G) + \gamma_{st}(\overline{G}) \leq n+2\). These bounds are sharp.

Proof. Since G and \(\overline{G}\) have no isolated vertex, \(\Delta(G) < n-1\) and \(\Delta(\overline{G}) < n-1\). Since \(\gamma_{st}(G) \geq 2\) and \(\gamma_{st}(\overline{G}) \geq 2\), the lower bound follows. To show the sharpness we prove a stronger result. Equality for the lower bound holds if and only if both G and \(\overline{G}\) are double-star by Observation 3.2. Thus \(G = \overline{G} = P_4\). We next establish the upper bound. By Proposition 3.2,

\[\gamma_{st}(G) + \gamma_{st}(\overline{G}) \leq n + 1 - \Delta(G) + n + 1 - \Delta(\overline{G})\] \[\leq n + 1 - \Delta(G) + n + 1 - (n - 1 - \delta(G))\] \[\leq n + 3 - \Delta(G) + \delta(G)\] \[\leq n + 3.\]

If \(\gamma_{st}(G) + \gamma_{st}(\overline{G}) = n+3\) then all inequalities in the above become equalities. In particular, \(\Delta(G) = \delta(G)\), and thus G is a regular graph. By Theorem 2.1,

\[n+3 = \gamma_{st}(G) + \gamma_{st}(\overline{G}) = \gamma_t(G) + \gamma_t(\overline{G}) \le n+2,\]

a contradiction. Thus \(\gamma_{st}(G) + \gamma_{st}(\overline{G}) \leq n+2\). To see the sharpness, let \(G = mK_2\) for some m > 1.

Similarly we obtain the following.

Theorem 3.6. Let G be a graph of order n. If G and \(\overline{G}\) have no isolated vertex then \(4 \le \gamma_{st}(G)\gamma_{st}(\overline{G}) \le (n-2)^2\). Both bounds are sharp for \(G = P_4\).

3.2. Sharp bounds on the strong total domination number in trees

Chellali et al. [3] obtained bounds on the weak total domination number of a tree T in terms of the order and the number of support vertices and leaves of T. Here, we present sharp upper and lower bounds for the strong total domination number of a tree T in terms of the order and the number of support vertices and leaves of T.

Theorem 3.7. For any tree T of order n ≥ 4 with l leaves and s support vertices,

\[\frac{n+2-l}{2} \le \gamma_{st}(T) \le \frac{n+s}{2}.\]

These bounds are sharp.

Proof. For the lower bound, by Theorem 2.3, γst(T) ≥ γt(T) ≥ n+2−l 2 . To see the sharpness consider a path P4. We next establish the upper bound. We proceed by induction on the order n. It is a routine matter to check that if 2 ≤ diam(T) ≤ 5 then γst(T) = γt(T) and thus the result is valid by Theorem 2.2. This establishes the base case. Assume the result is valid for any tree T ⁰ of order n ⁰ < n, and T has n vertices and s support vertices. Let x and y be two leaves with d(x, y) = diam(T). We assume that diam(T) ≥ 6. We root T at x. Let y¹ be the parent of y, y² the parent of y1, y³ the parent of y2, and y⁴ the parent of y3.

Assume first that deg(y2) ≥ 3. Let T¹ be the component of T − y1y² containing y2. Then y² is either a support vertex in T¹ or is adjacent to a support vertex. Let S¹ be a minimum std-set for T1. We may assume that y² ∈ S. Then S¹ ∪ {y1} is a std-set for T. By the inductive hypothesis

\[\gamma_{st}(T) \le \gamma_{st}(T_1) + 1 \le \frac{(n - \deg(y_1)) + s - 1}{2} + 1 = \frac{n - \deg(y_1) + s + 1}{2} < \frac{n + s}{2}.\]

Next assume that deg(y2) = 2.

If deg(y3) ≥ 3 then we let T² be the component of T −y2y³ containing y3. Let S² be a minimum std-set for T2. Then S² ∪ {y1, y2} is a std-set for T. By the inductive hypothesis

\[\gamma_{st}(T) \le \gamma_{st}(T_2) + 2 \le \frac{(n - \deg(y_1) - 1) + s - 1}{2} + 2 = \frac{n - \deg(y_1) + s + 2}{2} \le \frac{n + s}{2}\]

Thus we assume that deg(y3) = 2.

let T³ be the component of T − y3y⁴ containing y4. Let S³ be a minimum std-set for T3. Then S² ∪ {y1, y2} is a std-set for T. By the inductive hypothesis

\[\gamma_{st}(T) \le \gamma_{st}(T_3) + 2 \le \frac{(n - \deg(y_1) - 2) + s}{2} + 2 = \frac{n - \deg(y_1) + s + 2}{2} \le \frac{n + s}{2}.\]

To see the sharpness consider a path P6.

Acknowledgement

This research is supported by Islamic Azad University, Estahban Branch.

.

References

• [1] M. Chellali and T. W. Haynes, A note on the total domination of a tree, J. Combin. Math. Combin. Comput. 58 (2006), 189-193.
• [2] M. Chellali and T. W. Haynes, Total and paired-domination numbers of a tree, AKCE Int. J. Graphs Comb. 1 (2004), no. 2, 69-75.
• [3] M. Chellali and N. Jafari Rad, Weak total domination in graphs, Utilitas Mathematica 94 (2014), 221–236.
• [4] E.J. Cockayne, R.M. Dawes, S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), 211–219.
• [5] J. H. Hattingh and M. A. Henning, On strong domination in graphs, J. Combin. Math. Combin. Comput. 26 (1998), 73–92.
• [6] J. H. Hattingh and R. C. Laskar, On weak domination in graphs, Ars Combinatoria 49 (1998).
• [7] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
• [8] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, Inc., New York, 1998.
• [9] M. Krzywkowski, On trees with double domination number equal to total domination number plus one, Ars Combinatoria 102 (2011), 3-10.
• [10] M. Krzywkowski, On the ratio between 2-domination and total outer-independent domination numbers of trees, Chinese Annals of Mathematics, Series B 34 (2013), 765-776.
• [11] E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175–177.
• [12] D. Rautenbach, Bounds on the weak domination number, Australas. J. Combin. 18 (1998), 245–251.
• [13] D. Rautenbach, Bounds on the strong domination number, Discrete Math. 215 (2000), 201– 212.
• [14] E. Sampathkumar and L. Pushpa Latha, Strong, weak domination and domination balance in graphs, Discrete Math. 161 (1996), 235–242.