Distance paired domination numbers of graphs

In this paper, we study a generalization of the paired domination number. Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The k-distance paired domination number is the cardinality of a smallest k-distance paired dominating set of G. We investigate properties of the k-distance paired domination number of a graph. We also give an upper bound and a lower bound on the k-distance paired domination number of a non-trivial tree T in terms of the size of T and the number of leaves in T and we also characterize the extremal trees.     

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

Total domination and total domination subdivision number of a graph and its complement

A set S of vertices of a graph G=(V,E) with no isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγ_t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision numbersd_γt(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n?4, minimum degree δ and maximum degree Δ. We prove that if each component of G and has order at least 3 and , then and if each component of G and has order at least 2 and at least one component of G and has order at least 3, then . We also give a result on stronger than a conjecture by Harary and Haynes.     

Total restrained domination numbers of trees

For a given connected graph G=(V,E), a set D_tr⊆V(G) is a total restrained dominating set if it is dominating and both 〈D_tr〉 and 〈V(G)-D_tr〉 do not contain isolate vertices. The cardinality of the minimum total restrained dominating set in G is the total restrained domination number and is denoted by γ_tr(G). In this paper we characterize the trees with equal total and total restrained dominating numbers and give a lower bound on the total restrained dominating number of a tree T in terms of its order and the number of leaves of T.     

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.     

Bounds on cost effective domination numbers

A vertex υ in a set S is said to be cost effective if it is adjacent to at least as many vertices in V\S as it is in S and is very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is (very) cost effective if every vertex in S is (very) cost effective. The minimum cardinality of a (very) cost effective dominating set of G is the (very) cost effective domination number of G. Our main results include a quadratic upper bound on the very cost effective domination number of a graph in terms of its domination number. The proof of this result gives a linear upper bound for hereditarily sparse graphs which include trees. We show that no such linear bound exists for graphs in general, even when restricted to bipartite graphs. Further, we characterize the extremal trees attaining the bound. Noting that the very cost effective domination number is bounded below by the domination number, we show that every value of the very cost effective domination number between these lower and upper bounds for trees is realizable. Similar results are given for the cost effective domination number.     

On the sum of the total domination numbers of a digraph and its converse

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S has an in-neighbor in S. A dominating set S of D is called a total dominating set of D if the subdigraph induced by S has no isolated vertices. The total domination number of D, denoted by γt(D), is the minimum cardinality of a total dominating set of D. We show that for any connected digraph D of order n≥3, γt(D)+γt(D^? )≤5n/3, where D? is the converse of D. Furthermore, we characterize the oriented trees for which the equality holds.     

Changing and unchanging domination: a classification

The six classes of graphs resulting from the changing or unchanging of the domination number of a graph when a vertex is deleted, or an edge is deleted or added are considered. Each of these classes has been studied individually in the literature. We consider relationships among the classes, which are illustrated in a Venn diagram. We show that no subset of the Venn diagram is empty for arbitrary graphs, and prove that some of the subsets are empty for connected graphs. Our main result is a characterization of trees in each subset of the Venn diagram.     

On the domination number of the cartesian product of the cycle of length n and any graph

Let γ(G) denote the domination number of a graph G and let C_n□G denote the cartesian product of C_n, the cycle of length n?3, and G. In this paper, we are mainly concerned with the question: which connected nontrivial graphs satisfy γ(C_n□G)=γ(C_n)γ(G)? We prove that this equality can only hold if n≡1 (mod 3). In addition, we characterize graphs which satisfy this equality when n=4 and provide infinite classes of graphs for general n≡1 (mod 3).     

Stratification and domination in graphs II

A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class.) We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F rooted at v. In this paper we investigate the F-domination number when (i) F is a 2-stratified path P₃ on three vertices rooted at a blue vertex which is a vertex of degree 1 in the P₃ and is adjacent to a blue vertex and with the remaining vertex colored red, and (ii) F is a 2-stratified K₃ rooted at a blue vertex and with exactly one red vertex.     

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.     

The ratio of the distance irredundance and domination numbers of a graph

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n-dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n-dominating sets of G is called the n-domination number of G and is denoted by γ_n(G). A set / of vertices in G is n-irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / - {x}. The n-irredundance number of G, denoted by ir_n(G), is the minimum cardinality taken over all maximal n-irredundant sets of vertices of G. We show that inf{ir_n(G)/γ_n(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_n(T)/γ_n(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph-Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

Construction of trees and graphs with equal domination parameters

We provide a simple constructive characterization for trees with equal domination and independent domination numbers, and for trees with equal domination and total domination numbers. We also consider a general framework for constructive characterizations for other equality problems.     

Global italian domination in graphs

Abstract

An Italian dominating function (IDF) on a graph G = (V, E) is a function f: V → {0, 1, 2} satisfying the condition that for every vertex v ∈ V (G) with f (v) = 0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to at least two vertices assigned 1. The weight of an IDF f is the value ∑_v∈V(G) f (v). The Italian domination number of a graph G, denoted by γ_I (G), is the minimum weight of an IDF on G. An IDF f on G is called a global Italian dominating function (GIDF) on G if f is also an IDF on the complement ? of G. The global Italian domination number of G, denoted by γ_gI (G), is the minimum weight of a GIDF on G. In this paper, we initiate the study of the global Italian domination number and we present some strict bounds for the global Italian domination number. In particular, we prove that for any tree T of order n ≥ 4, γ_gI (T) ≤ γ_I (T) + 2 and we characterize all trees with γ_gI (T) = γ_I (T) + 2 and γ_gI (T) = γ_I (T) + 1.     

Domination versus disjunctive domination in graphs

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number of G is the minimum cardinality of a dominating set of G. For a positive integer b, a set S of vertices in a graph G is a b-disjunctive dominating set in G if every vertex v not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it in G. The b-disjunctive domination number of G is the minimum cardinality of a b-disjunctive dominating set. In this paper, we continue the study of disjunctive domination in graphs. We present properties of b-disjunctive dominating sets in a graph. A characterization of minimal b-disjunctive dominating sets is given. We obtain bounds on the ratio of the domination number and the b-disjunctive domination number for various families of graphs, including regular graphs and trees.     

Irredundance, secure domination and maximum degree in trees

It is shown that the lower irredundance number and secure domination number of an n vertex tree T with maximum degree Δ?3, are bounded below by 2(n+1)/(2Δ+3)(T≠K_1,Δ) and (Δn+Δ-1)/(3Δ-1), respectively. The bounds are sharp and extremal trees are exhibited.     

Characterization of double domination subdivision number of trees

In a graph G, a vertex dominates itself and its neighbors. A subset S⊆V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The double domination numberdd(G) is the minimum cardinality of a double dominating set of G. The double domination subdivision numbersd_dd(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the double domination number. In this paper first we establish upper bounds on the double domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that sd_dd(G)?3. We also prove that 1?sd_dd(T)?2 for every tree T, and characterize the trees T for which sd_dd(T)=2.     

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