Search

Let D be a finite and simple digraph with vertex set V (D). A Roman dominating function (RDF) on a digraph D is a function f : V (D) → {0, 1, 2} satisfying the condition that every vertex v with f (v) = 0 has an in-neighbor u with f (u) = 2. The weight of an RDF f is the value. An RDF f on D with no isolated vertex is called a total Roman dominating function if the subdigraph of D induced by the set {v ∈ V (D): f (v) ≠ 0} has no isolated vertex. The Roman domination number is the minimum weight of a total Roman dominating function on D. In this paper, we initiate the study of the total Roman domination number in digraphs and show its relationship to other domination parameters. In particular, we present some sharp bounds for the total Roman domination number and we determine the total Roman domination number of some classes of digraphs. [ABSTRACT FROM AUTHOR]

In this paper, we study a parameter that is a relaxation of an important domination parameter, namely the paired domination. A set D of vertices in G is a semipaired dominating set of G if it is a dominating set of G and can be partitioned into 2-element subsets such that the vertices in each 2-set are at most distance two apart. The semipaired domination number, γpr2(G), is the minimum cardinality of a semipaired dominating set of G. For a graph G without isolated vertices, the domination number γ(G), the paired domination number γpr(G) and the semitotal domination number γt2(G) are related to the semipaired domination numbers by the following inequalities: γ(G) ≤ γt2(G) ≤ γpr2(G) ≤ γpr(G) ≤ 2γ(G). It means that 1 ≤ γpr2(G)/γ(G) ≤ 2. In this paper, we characterize those trees that attain the lower bound and the upper bound, respectively. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A vertex subsetSof a digraphDis called a dominating set ofDif every vertex not inSis adjacent from at least one vertex inS. A dominating setSofDis called a total dominating set ofDif the subdigraph ofDinduced by S has no isolated vertices. The total domination number ofD, denoted byγt(D), is the minimum cardinality of a total dominating set ofD. In this note, we introduce a new parameter, called the out-Slater number of a digraphD, which is defined by, whereare the firstklargest out-degrees ofD. Then we prove that ifDis a digraph of ordernwith maximum out-degree Δ+and with no isolated vertices, thenγt(D) ≥sℓ+(D) ≥ ⌈2n/(2Δ++ 1)⌉ and the difference betweensℓ+(D) and ⌈2n/(2Δ++ 1)⌉ can be arbitrarily large, which improves a known lower bound by Arumugam et al. In particular, for an oriented treeTof ordern≥ 2 withn0vertices of out-degree 0, we show thatγt(T) ≥sℓ+(T) ≥ 2(n−n0+ 1)/3 and the difference betweensℓ+(T) and 2(n−n0+ 1)/3 is also arbitrarily large. [ABSTRACT FROM AUTHOR]

A vertex subsetSof a digraphDis called a dominating set ofDif every vertex not inSis adjacent from at least one vertex inS. A dominating setSofDis called a total dominating set ofDif the subdigraph ofDinduced byShas no isolated vertices. The total domination number ofD, denoted byγt(D), is the minimum cardinality of a total dominating set ofD. We show that ifDis a rooted tree, a connected contrafunctional digraph or a strongly connected digraph of ordern≥ 2, thenγt(D) ≤ 2(n+ 1)/3 and ifDis a digraph of order n with minimum in-degree at least one whose connected components are isomorphic to neithernor, thenγt(D) ≤ 3n/4, whereanddenote the directed cycles of order 2 and 5 respectively. Moreover, we characterize the corresponding digraphs achieving these upper bounds. [ABSTRACT FROM AUTHOR]