Lower bounds on several versions of signed domination number

Three numerical invariants of graphs concerning domination, which are named the signed domination number γ_s, the k-subdomination number γ_ks and the signed total domination number γ_st, are studied in this paper. For any graph, some lower bounds on γ_s, γ_ks and γ_st are presented, some of which generalize several known lower bounds on γ_s, γ_ks and γ_st, while others are considered as new. It is also shown that these bounds are sharp.     

Total domination subdivision numbers of trees

A set S of vertices in a graph G is a total dominating set of G if every vertex is adjacent to a vertex in S. The total domination number γ_t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt(G) of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. Haynes et al. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, 1?sd_γt(T)?3. In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3.     

A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

Properties of total domination edge-critical graphs

A set S of vertices in a graph G is a total dominating set of G 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 γ_t(G) of G. The graph G is total domination edge critical if for every edge e in the complement of G, γ_t(G+e)<γ_t(G). We call such graphs γ_tEC. Properties of γ_tEC graphs are established.     

Power domination in graphs

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 1998, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number γ_P(G) of a graph G is the minimum cardinality of a power dominating set of G. In this paper, we present upper bounds on the power domination number for a connected graph with at least three vertices and a connected claw-free cubic graph in terms of their order. The extremal graphs attaining the upper bounds are also characterized.     

Matching properties in connected domination critical graphs

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].     

The signed star domination numbers of the Cartesian product graphs

Let G be a graph with vertex set V(G) and edge set E(G). A function f:E(G)→{-1,1} is said to be a signed star dominating function of G if for every v∈V(G), where E_G(v)={uv∈E(G)|u∈V(G)}. The minimum of the values of , taken over all signed star dominating functions f on G, is called the signed star domination number of G and is denoted by γ_SS(G). In this paper, a sharp upper bound of γ_SS(G×H) is presented.     

On equality in an upper bound for the restrained and total domination numbers of a graph

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S and to a vertex in V?S. The restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of an RDS of G. A set S⊆V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γ_t(G), is the minimum cardinality of a TDS of G.Let δ and Δ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ?2, then it is shown that γ_r(G)?n-Δ, and we characterize the connected graphs with δ?2 achieving this bound that have no 3-cycle as well as those connected graphs with δ?2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211-219] showed that if G is a connected graph of order n?3 and Δ?n-2, then γ_t(G)?n-Δ. We further characterize the connected graphs G of order n?3 with Δ?n-2 that have no 3-cycle and achieve γ_t(G)=n-Δ.     

The diameter of total domination vertex critical graphs

A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G. These graphs we call γ_t-critical. If such a graph G has total domination number k, we call it k-γ_t-critical. We characterize the connected graphs with minimum degree one that are γ_t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γ_t-critical graph for k?8 and provide an example which shows that the maximum diameter is in general at least 5k/3-O(1).     

Lower bounds for the domination number and the total domination number of direct product graphs

A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: . Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γ_t(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made.     

On total domination vertex critical graphs of high connectivity

A graph is called γ-critical if the removal of any vertex from the graph decreases the domination number, while a graph with no isolated vertex is γ_t-critical if the removal of any vertex that is not adjacent to a vertex of degree 1 decreases the total domination number. A γ_t-critical graph that has total domination number k, is called k-γ_t-critical. In this paper, we introduce a class of k-γ_t-critical graphs of high connectivity for each integer k≥3. In particular, we provide a partial answer to the question “Which graphs are γ-critical and γ_t-critical or one but not the other?” posed in a recent work [W. Goddard, T.W. Haynes, M.A. Henning, L.C. van der Merwe, The diameter of total domination vertex critical graphs, Discrete Math. 286 (2004) 255-261].     

Signed star domatic number of a graph

Let G be a simple graph without isolated vertices with vertex set V(G) and edge set E(G). A function f:E(G)?{−1,1} is said to be a signed star dominating function on G if ∑_e∈E(v)f(e)≥1 for every vertex v of G, where E(v)={uv∈E(G)∣u∈N(v)}. A set {f₁,f₂,…,f_d} of signed star dominating functions on G with the property that for each e∈E(G), is called a signed star dominating family (of functions) on G. The maximum number of functions in a signed star dominating family on G is the signed star domatic number of G, denoted by d_SS(G).In this paper we study the properties of the signed star domatic number d_SS(G). In particular, we determine the signed domatic number of some classes of graphs.     

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.     

On the bondage number of middle graphs

Let G = (V (G),E(G)) be a simple graph. A subset S of V (G) is a dominating set of G if, for any vertex v ∈ V (G) — S, there exists some vertex u ∈ S such that uv ∈ E(G). The domination number, denoted by γ(G), is the cardinality of a minimal dominating set of G. There are several types of domination parameters depending upon the nature of domination and the nature of dominating set. These parameters are bondage, reinforcement, strong-weak domination, strong-weak bondage numbers. In this paper, we first investigate the strong-weak domination number of middle graphs of a graph. Then several results for the bondage, strong-weak bondage number of middle graphs are obtained.     

Bounds on total domination in claw-free cubic graphs

A set S of vertices in a graph G is a total dominating set, denoted by TDS, of G if every vertex of G is adjacent to some vertex in S (other than itself). The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_t(G). If G does not contain K_1,3 as an induced subgraph, then G is said to be claw-free. It is shown in [D. Archdeacon, J. Ellis-Monaghan, D. Fischer, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004) 207-210.] that if G is a graph of order n with minimum degree at least three, then γ_t(G)?n/2. Two infinite families of connected cubic graphs with total domination number one-half their orders are constructed in [O. Favaron, M.A. Henning, C.M. Mynhardt, J. Puech, Total domination in graphs with minimum degree three, J. Graph Theory 34(1) (2000) 9-19.] which shows that this bound of n/2 is sharp. However, every graph in these two families, except for K₄ and a cubic graph of order eight, contains a claw. It is therefore a natural question to ask whether this upper bound of n/2 can be improved if we restrict G to be a connected cubic claw-free graph of order at least 10. In this paper, we answer this question in the affirmative. We prove that if G is a connected claw-free cubic graph of order n?10, then γ_t(G)?5n/11.     

Matching Properties in Total Domination Vertex Critical Graphs

A vertex subset S of a graph G = (V,E) is a total dominating set if every vertex of 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. A graph G with no isolated vertex is said to be total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ _t (G?v) < γ _t (G). A total domination vertex critical graph G is called k-γ _t -critical if γ _t (G) = k. In this paper we first show that every 3-γ _t -critical graph G of even order has a perfect matching if it is K _1,5-free. Secondly, we show that every 3-γ _t -critical graph G of odd order is factor-critical if it is K _1,5-free. Finally, we show that G has a perfect matching if G is a K _1,4-free 4-γ _t (G)-critical graph of even order and G is factor-critical if G is a K _1,4-free 4-γ _t (G)-critical graph of odd order.     

Dominating direct products of graphs

An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs G and H, γ(G×H)?3γ(G)γ(H). Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that Γ(G×H)?Γ(G)Γ(H), thus confirming a conjecture from [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Finally, for paired-domination of direct products we prove that γ_pr(G×H)?γ_pr(G)γ_pr(H) for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound.     

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.     

Total domination in claw-free graphs with minimum degree 2

A set S of vertices in a graph G is a total dominating set (TDS) of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_t(G). A graph is claw-free if it does not contain K_1,3 as an induced subgraph. It is known [M.A. Henning, Graphs with large total domination number, J. Graph Theory 35(1) (2000) 21-45] that if G is a connected graph of order n with minimum degree at least two and G∉{C₃,C₅, C₆, C₁₀}, then γ_t(G)?4n/7. In this paper, we show that this upper bound can be improved if G is restricted to be a claw-free graph. We show that every connected claw-free graph G of order n and minimum degree at least two satisfies γ_t(G)?(n+2)/2 and we characterize those graphs for which γ_t(G)=⌊(n+2)/2⌋.     

A note on acyclic domination number in graphs of diameter two

A subset S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by γ_a(G), is called the acyclic domination number of G. Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151-165] introduced the concept of acyclic domination and posed the following open problem: if δ(G) is the minimum degree of G, is γ_a(G)?δ(G) for any graph whose diameter is two? In this paper, we provide a negative answer to this question by showing that for any positive k, there is a graph G with diameter two such that γ_a(G)-δ(G)?k.