Search

A double Roman dominating function (DRDF) on a graph G = (V, E) is a function f : V(G) → {0, 1, 2, 3} having the property that if f(v) = 0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3, and if f(v) = 1, then vertex v must have at least one neighbor w with f(w) ≥ 2. A DRDF f is called a global double Roman dominating function (GDRDF) if f is also a DRDF of the complement of G. The weight of a GDRDF is the sum of its function value over all vertices. The global double Roman domination number of G, denoted by γgdR(G), is the minimum weight of a GDRDF on G. In this paper, we initiate the study of the global double Roman domination number. We obtain some properties of global double Roman domination number. [ABSTRACT FROM AUTHOR]

Let D = (V,A) be a finite simple digraph and N(uv) = {u'v' 6= uv | u = u' or v = v'} be the open neighbourhood of uv in D. A function f : A → {-1, +1} is said to be a signed arc total dominating function (SATDF) of D if ∑e'∈N(uv) f(e') ≥ 1 holds for every arc uv 2 A. The signed arc total domination number γ'st(D) is defined as γ'st(D) = min{∑e∈A f(e) | f is an SATDF of D}. In this paper we initiate the study of the signed arc total domination in digraphs and present some lower bounds for this parameter. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a simple graph with vertex set V and edge set E. A Roman dominating function on a graph G is a function f : V ( G ) → { 0 , 1 , 2 } satisfying the condition that every vertex u for which f ( u ) = 0 is adjacent to at least one vertex v for which f ( v ) = 2. A Roman dominating function f is called an independent Roman dominating function if the set of all vertices with positive weights is an independent set. The weight of an independent Roman dominating function f is the value f ( V ( G ) ) = ∑ u ∈ V ( G ) f ( u ). The independent Roman domination number of G , denoted by i R ( G ) , is the minimum weight of an independent Roman dominating function on G. A subset S of V is a 2-independent set of G if every vertex of S has at most one neighbor in S. The maximum cardinality of a 2-independent set of G is the 2-independence number β 2 ( G ). These two parameters are incomparable in general, however, we show that for any tree T , β 2 ( T ) ≥ i R ( T ) and we characterize all trees attaining the equality. [ABSTRACT FROM AUTHOR]

A total Roman dominating function (TRDF) on a graph is a function satisfying the conditions (i) every vertex for which is adjacent at least one vertex for which and (ii) the subgraph of induced by the set of all vertices of positive weight has no isolated vertex. The weight of a TRDF is the sum of its function values over all vertices. A total Roman dominating function is called a global total Roman dominating function (GTRDF) if is also a TRDF of the complement of . The global total Roman domination number of is the minimum weight of a GTRDF on . In this paper, we initiate the study of global total Roman domination number and investigate its basic properties. In particular, we relate the global total Roman domination and the total Roman domination and the global Roman domination number. [ABSTRACT FROM AUTHOR]

For a positive integer k, a k-rainbow dominating function (kRDF) of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set {1,2,. . .,k} such that for any vertex υ ϵ V(G) with f (υ )= ∅, the condition ∪uϵN(υ ) f ( υ ) ={1,2,. . .,k} is fulfilled, where N(υ ) is the neighborhood of v. The weight of a kRDF f is the value ω(f )= Συ ϵV∣f( υ)∣. A kRDF f is called a global k-rainbow dominating function (GkRDF) if f is also a kRDF of the complement G̅ of G. The global k-rainbow domination number of G, denoted by γgrk(G), is the minimum weight of a GkRDF on G. In this paper, we initiate the study of the global k-rainbow domination number and we establish some sharp bounds for it. [ABSTRACT FROM AUTHOR]

Let D be a simple digraph with arc set A(D), and let j and k be two positive integers. A function f : A(D) → {-1, 1} is said to be a signed star j-dominating function (SSjDF) on D if ∑a ∈ A(v) f(a) ≥ j for every vertex v of D, where A(v) is the set of arcs with head v. A set {f1, f2, ..., fd} of distinct SSjDFs on D with the property that for each a ∈ A(D), is called a signed star (j, k)-dominating (SS(j, k)D) family (of functions) on D. The maximum number of functions in a SS(j, k)D family on D is the signed star (j, k)-domatic number of D, denoted by . In this paper, we study properties of the signed star (j, k)-domatic number of a digraph D. In particular, we determine bounds on . Some of our results extend these ones given by Sheikholeslami and Volkmann [Signed star k-domination and k-domatic number of digraphs, submitted] for the signed (j, 1)-domatic number. [ABSTRACT FROM AUTHOR]

A 2-rainbow dominating function (2RDF) on a graph G = (V, E) is a function ƒ from the vertex set V to the set of all subsets of the set {1, 2} such that for any vertex v ∈ V with ƒ(v) = ø the condition ∪u∈N(v) ƒ(u) = {1, 2} is fulfilled. A 2RDF ƒ is independent (I2RDF) if no two vertices assigned nonempty sets are adjacent. The weight of a 2RDF ƒ is the value ω(ƒ) = Σu∈V ǀƒ(v)ǀ. The 2-rainbow domination number γr2(G) (respectively, the independent 2-rainbow domination number ir2(G)) is the minimum weight of a 2RDF (respectively, I2RDF) on G. We say that βr2(G) is strongly equal to ir2(G) and denote by βr2(G) ≣ ir2(G), if every 2RDF on G of minimum weight is an I2RDF. In this paper we characterize all unicyclic graphs G with βr2(G) r2 ir2(G). [ABSTRACT FROM AUTHOR]

A 2-rainbow dominating function (2RDF) of a graph G is a function f from the vertex set V (G) to the set of all subsets of the set {1,2} such that for any vertex v ∊ V(G) with f(v) = ϕ the condition ∪u∊N(v)f(u) = {1, 2} is fulfilled. The weight of a 2RDF f is the value ω(f) = ∑v∊V∣f(v)∣. The 2-rainbow domination number of a graph G, denoted by γr2(G), is the minimum weight of a 2RDF of G. The 2-rainbow domination subdivision number sdγr2(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 2-rainbow domination number. In this paper, we initiate the study of 2-rainbow domination subdivision number in graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple graph without isolated vertices with vertex set V(G) and edge set E(G) and let k be a positive integer. A function f : E(G) → { -1,1} is said to be a signed star k-dominating function on G if ∑e∈E(v) f(e) ≥ k for every vertex v of G, where E(v) = {uv ∈ E(G) | u ∈ N(v)}. A set {f1, f2,... , fd} of signed star k-dominating functions on G with the property that ∑i=1d fi(e) ≤ k for each e ∈ E(G), is called a signed star (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed star (k, k)-dominating family on G is the signed star (k, k)-domatic number of G, denoted by dSS(k,k) (G). In this paper we study properties of the signed star (k, k)-domatic number dSS(k,k) (G). In particular, we present bounds on dSS(k,k) (G), and we determine the signed (k, k)-domatic number of some regular graphs. Some of our results extend these given by Atapour, Sheikholeslami, Ghameslou and Volkmann [Signed star domatic number of a graph, Discrete Appl. Math. 158 (2010), 213-218] for the signed star domatic number. [ABSTRACT FROM AUTHOR]

A function ƒ : V (G) → {-1, 0, 1} is a minus dominating function if for every vertex v ϵ V (G), ΣuϵN[v] ƒ(u) ≥ 1. A minus dominating function ƒ of G is called a global minus dominating function if ƒ is also a minus dominating function of the complement Ḡ of G. The global minus domination number γg-(G) of G is defined as γg-(G) = min{ΣvϵV(G) ƒ(v) | ƒ is a global minus dominating function of G}. In this paper we initiate the study of the global minus domination number in graphs and we establish lower and upper bounds for the global minus domination number. [ABSTRACT FROM AUTHOR]

Let G be a simple graph without isolated vertices with edge set E(G), and let j and k be two positive integers. A function f : E(G) → {-1, 1} is said to be a signed star j-dominating function on G if ∑e∈E(v) f(e) ≥ j for every vertex v of G, where E(v) = {uv ∈ E(G) | u ∈ N(v)}. A set {f1, f2, . . ., fd} of distinct signed star j-dominating functions on G with the property that ∑i=1dfi(e) ≤ k for each e ∈ E(G), is called a signed star (j, k)-dominating family (of functions) on G. The maximum number of functions in a signed star (j, k)-dominating family on G (j, k) is the signed star (j, k)-domatic number of G denoted by dS S(j, k) (G). In this paper we study properties of the signed star (j, k)-domatic number of (j, k) a graph G. In particular, we determine bounds on dS S(j, k)(G). Some of our results extend those ones given by Atapour, Sheikholeslami, Ghameslou and Volkmann [1] for the signed star domatic number, Sheikholeslami and Volkmann [5] for the signed star (k, k)-domatic number and Sheikholeslami and Volkmann [4] for the signed star k-domatic number. [ABSTRACT FROM AUTHOR]

In this paper we initiate the study of signed total distance k-domatic numbers in graphs and we present its sharp upper bounds. [ABSTRACT FROM AUTHOR]

For a positive integer k, a total {k}-dominating function of a graph G without isolated vertices is a function f from the vertex set V(G) to the set {0,1,2, . . . ,k} such that for any vertex v ∊ V(G), the condition Σu∊N(v) f (u) ≥ k is fulfilled, where N(v) is the open neighborhood of v. The weight of a total {k}-dominating function f is the value ω(f) = Σv∊V f (v). The total {k}-domination number, denoted by γt{k} (G), is the minimum weight of a total {k}-dominating function on G. A set {f1, f2, . . . , fd} of total {k}-dominating functions on G with the property that Σdi =1 fi(v) ≤ k for each v ∊ V(G), is called a total {k}-dominating family (of functions) on G. The maximum number of functions in a total {k}-dominating family on G is the total {k}-domatic number of G, denoted by dt{k} (G). Note that dt{1} (G) is the classic total domatic number dt(G). In this paper, we present bounds for the total {k}-domination number and total {k}-domatic number. In addition, we determine the total {k}-domatic number of cylinders and we give a Nordhaus-Gaddum type result. [ABSTRACT FROM AUTHOR]

Let D be a finite and simple digraph with vertex set V(D), and let f : V(D)→ {-1,1} be a two-valued function. If k ≥ 1 is an integer and Σα∊N-[v] f (x) ≤ k for each v ∊V(D), where N-[v] consists of v and all vertices of D from which arcs go into v, then f is a signed k-dominating function on D. A set {f1, f2, ..., fd} of distinct signed k-dominating functions of D with the property that Σdi=1 fi(v) ≤ 1 for each v ∊ V(D), is called a signed k-dominating family (of functions) of D. The maximum number of functions in a signed k-dominating family of D is the signed k-domatic number of D, denoted by dkS(D). In this note we initiate the study of the signed k-domatic numbers of digraphs and present some sharp upper bounds for this parameter. [ABSTRACT FROM AUTHOR]

Let D be a finite and simple digraph with vertex set V(D). A twin Roman dominating function (TRDF) on D is a labeling f W V(D) → {0,1,2}g such that every vertex with label 0 has an in-neighbor and out-neighbor with label 2. The weight of a TRDF f is the value w(f)= ΣvεV(D) f (v). The twin Roman domination number of a digraph D, denoted by γR(D), equals the minimum weight of a TRDF on D. In this paper we initiate the study of the twin Roman domination number in digraphs. In particular, we present sharp bounds for γR(D) and determine the exact value of the twin Roman domination number for some classes of digraphs. [ABSTRACT FROM AUTHOR]