Remarks on restrained domination and total restrained domination in graphs

The restrained domination number ^r(G) and the total restrained domination number _t ^r (G) of a graph G were introduced recently by various authors as certain variants of the domination number (G) of (G). A well-known numerical invariant of a graph is the domatic number d(G) which is in a certain way related (and may be called dual) to (G). The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.This research was supported by Grant MSM 245100303 of the Ministry of Education, Youth and Sports of the Czech Republic.     

On total restrained domination in graphs

In this paper we initiate the study of total restrained domination in graphs. Let G = (V,E) be a graph. A total restrained dominating set is a set S V where every vertex in V - S is adjacent to a vertex in S as well as to another vertex in V - S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by _r ^t (G), is the smallest cardinality of a total restrained dominating set of G. First, some exact values and sharp bounds for _r ^t (G) are given in Section 2. Then the Nordhaus-Gaddum-type results for total restrained domination number are established in Section 3. Finally, we show that the decision problem for _r ^t (G) is NP-complete even for bipartite and chordal graphs in Section 4.This work was supported by National Natural Sciences Foundation of China (19871036).     

Total restrained domination in trees

Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-S is adjacent to a vertex in V-S. The total restrained domination number of G, denoted by γ_tr(G), is the smallest cardinality of a total restrained dominating set of G. We show that if T is a tree of order n, then . Moreover, we show that if T is a tree of order , then . We then constructively characterize the extremal trees T of order n achieving these lower bounds.     

Total domination dot-stable graphs

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most 2. A graph is total domination dot-stable if dotting any pair of adjacent vertices leaves the total domination number unchanged. We characterize the total domination dot-stable graphs and give a sharp upper bound on their total domination number. We also characterize the graphs attaining this bound.     

A note on total reinforcement in graphs

In this note we prove a conjecture and improve some results presented in a recent paper of Sridharan et al. [N. Sridharan, M.D. Elias, V.S.A. Subramanian, Total reinforcement number of a graph, AKCE Int. J. Graphs Comb. 4 (2) (2007) 197-202].     

Total Restrained Domination in Cubic Graphs

A set S of vertices in a graph G = (V, E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. Let G be a cubic graph of order n. In this paper we establish an upper bound on γ _tr (G). If adding the restriction that G is claw-free, then we show that γ _tr (G) = γ _t (G) where γ _t (G) is the total domination number of G, and thus some results on total domination in claw-free cubic graphs are valid for total restrained domination. Research was partially supported by the NNSF of China (Nos. 60773078, 10832006), the ShuGuang Plan of Shanghai Education Development Foundation (No. 06SG42) and Shanghai Leading Academic Discipline Project (No. S30104).     

A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

Unique response Roman domination in graphs

A function f:V(G)→{0,1,2} is a Roman dominating function if every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. A function f:V(G)→{0,1,2} with the ordered partition (V₀,V₁,V₂) of V(G), where V_i={v∈V(G)∣f(v)=i} for i=0,1,2, is a unique response Roman function if x∈V₀ implies |N(x)∩V₂|≤1 and x∈V₁∪V₂ implies that |N(x)∩V₂|=0. A function f:V(G)→{0,1,2} is a unique response Roman dominating function if it is a unique response Roman function and a Roman dominating function. The unique response Roman domination number of G, denoted by u_R(G), is the minimum weight of a unique response Roman dominating function. In this paper we study the unique response Roman domination number of graphs and present bounds for this parameter.     

Total minus domination in k-partite graphs

A function f defined on the vertices of a graph G=(V,E),f:V→{-1,0,1} is a total minus dominating function (TMDF) if the sum of its values over any open neighborhood is at least one. The weight of a TMDF is the sum of its function values over all vertices. The total minus domination number, denoted by , of G is the minimum weight of a TMDF on G. In this paper, a sharp lower bound on of k-partite graphs is given.     

Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs

Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-S is adjacent to a vertex in V-S. A set S⊆V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The total restrained domination number of G (restrained domination number of G, respectively), denoted by γ_tr(G) (γ_r(G), respectively), is the smallest cardinality of a total restrained dominating set (restrained dominating set, respectively) of G. We bound the sum of the total restrained domination numbers of a graph and its complement, and provide characterizations of the extremal graphs achieving these bounds. It is known (see [G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69.]) that if G is a graph of order n?2 such that both G and are not isomorphic to P₃, then . We also provide characterizations of the extremal graphs G of order n achieving these bounds.     

k-Subdomination in graphs

For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f : V→{−1,1} such that ∑_uNG[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ_ks(G), is the minimum of ∑_vVf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ_ks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ_ks(G), the signed domination number γ_s(G) and the majority domination number γ_maj(G).     

Disjoint dominating and total dominating sets in graphs

It has been shown [M.A. Henning, J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159-162] that every connected graph with minimum degree at least two that is not a cycle on five vertices has a dominating set D and a total dominating set T which are disjoint. We characterize such graphs for which D∪T necessarily contains all vertices of the graph and that have no induced cycle on five vertices.     

阶数极大的临界全控制图

称一个没有孤立点的图G 为临界全控制图, 如果G 满足对于任何一个不与悬挂点相邻的顶点v, G - v 的全控制数都小于G 的全控制数. 如果G 的全控制数记为γ_t, 则称这样的临界全控制图G 为γ_t- 临界的. 如果G 是γ_t- 临界的, 且阶数为n, 则n ≤ Δ(G)(γ_t(G)- 1) + 1, 其中Δ(G) 是G 的最大度. 本文将证明对γ_t = 3, 这个阶数的上界是紧的, 并给出所有满足n = Δ(G)(γ_t(G)- 1) + 1 的3-γ_t- 临界图.     

Total domination in graphs with minimum degree three

A set S of vertices of a graph G is a total dominating set, if every vertex of V(G) is adjacent to some vertex in S. The total domination number of G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at least 3, then γ_t(G) ≤ 7n/13. © 2000 John Wiley & Sons, Inc. J Graph Theory 34:9–19, 2000     

On global domination critical graphs

A dominating set of a graph G=(V,E) is a subset S⊆V such that every vertex not in S is adjacent to at least one vertex of S. The domination number of G is the cardinality of a smallest dominating set. The global domination number, γ_g(G), is the cardinality of a smallest set S that is simultaneously a dominating set of both G and its complement . Graphs for which γ_g(G−e)>γ_g(G) for all edges e∈E are characterized, as are graphs for which γ_g(G−e)<γ_g(G) for all edges e∈E whenever is disconnected. Progress is reported in the latter case when is connected.     

Broadcasts in graphs

We say that a function f:V→{0,1,…,diam(G)} is a broadcast if for every vertex v∈V, f(v)?e(v), where diam(G) denotes the diameter of G and e(v) denotes the eccentricity of v. The cost of a broadcast is the value . In this paper we introduce and study the minimum and maximum costs of several types of broadcasts in graphs, including dominating, independent and efficient broadcasts.