Given a graph G , we consider the Italian domination number γ I ( G ), the 2-rainbow domination number γ r 2 ( G ) and the Roman domination number γ R ( G ). It is known that γ I ( G ) ≤ γ r 2 ( G ) ...≤ γ R ( G ) holds for any graph G . In this paper, we prove that γ I ( M ( G )) = γ r 2 ( M ( G )) = γ R ( M ( G )) = n for the middle graph M ( G ) of a graph G of order n , which gives an answer for an open problem posed by Chellali et al . Discrete Appl. Math . 204 (2016) 22–28. Moreover, we give a complete characterization of Roman domination stable middle graphs, 2-rainbow domination stable middle graphs and Italian domination stable middle graphs.
Let k ∈ Z +. A k − distance Roman dominating function (kDRDF) on G = (V, E) is a function f : V → {0, 1, 2} such that for every vertex v with f(v) = 0, there is a vertex u with f(u) = 2 with d(u, v) ...≤ k. The function f is a global k − distance Roman dominating function (GkDRDF) on G if and only if f is a k − distance Roman dominating function (kDRDF) on G and on its complement G. The weight of the global k − distance Roman dominating function (GkDRDF) f is the value w(f) = P x∈V f(x). The minimum weight of the global k − distance Roman dominating function (GkDRDF) on the graph G is called the global k − distance Roman domination number of G and is denoted as γ k gR(G). A γ k gR(G) − function is the global k − distance Roman dominating function on G with weight γ k gR(G). Note that, the global 1 − distance Roman domination number γ 1 gR(G) is the usual global Roman domination number γgR(G), that is, γ 1 gR(G) = γgR(G). The authors initiated this study. In this paper, the authors obtained and established the following results: preliminary results on global distance Roman domination; the global distance Roman domination on Kn, Kn, Pn, and Cn; and, some bounds and characterizations of global distance Roman domination over any graphs.
Varieties of Roman domination II Chellali, M.; Jafari Rad, N.; Sheikholeslami, S. M. ...
AKCE international journal of graphs and combinatorics,
09/2020, Letnik:
17, Številka:
3
Journal Article
Recenzirano
Odprti dostop
In this work, we continue to survey what has been done on the Roman domination. More precisely, we will present in two sections several variations of Roman dominating functions as well as the signed ...version of some of these functions. It should be noted that a first part of this survey comprising 9 varieties is published as a chapter book in “Topics in domination in graphs” edited by T.W. Haynes, S.T. Hedetniemi and M.A. Henning. We recall that a function is a Roman dominating function (or just RDF) if every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The Roman domination number of a graph G, denoted by is the minimum weight of an RDF on G.
We continue the study of restrained double Roman domination in graphs. For a graph G=(V(G),E(G)), a double Roman dominating function f is called a restrained double Roman dominating function (RDRD ...function) if the subgraph induced by {v∈V(G)∣f(v)=0} has no isolated vertices. The restrained double Roman domination number (RDRD number) γrdR(G) is the minimum weight ∑v∈V(G)f(v) taken over all RDRD functions of G.
We first prove that the problem of computing γrdR is NP-hard even for planar graphs, but it is solvable in linear time when restricted to bounded clique-width graphs such as trees, cographs and distance-hereditary graphs. Relationships between γrdR and some well-known parameters such as restrained domination number γr, domination number γ or restrained Roman domination number γrR are investigated in this paper by bounding γrdR from below and above involving γr, γ or γrR for general graphs, respectively. We prove that γrdR(T)≥n+2 for any tree T≠K1,n−1 of order n≥2 and characterize the family of all trees attaining the lower bound. The characterization of graphs with small RDRD numbers is given in this paper.
We consider two general frameworks for multiple domination, which are called 〈r,s〉-domination and parametric domination. They generalise and unify {k}-domination, k-domination, total k-domination and ...k-tuple domination. In this paper, known upper bounds for the classical domination are generalised for the 〈r,s〉-domination and parametric domination numbers. These generalisations are based on the probabilistic method and they imply new upper bounds for the {k}-domination and total k-domination numbers. Also, we study threshold functions, which impose additional restrictions on the minimum vertex degree, and present new upper bounds for the aforementioned numbers. Those bounds extend similar known results for k-tuple domination and total k-domination.
On the Total k-Domination in Graphs Bermudo, Sergio; Hernández-Gómez, Juan C.; Sigarreta, José M.
Discussiones Mathematicae. Graph Theory,
01/2018, Letnik:
38, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Let
= (
) be a graph; a set
⊆
is a total
-dominating set if every vertex
∈
has at least
neighbors in
. The total
-domination number
) is the minimum cardinality among all total
-dominating sets. In ...this paper we obtain several tight bounds for the total
-domination number of a graph. In particular, we investigate the relationship between the total
-domination number of a graph and the order, the size, the girth, the minimum and maximum degree, the diameter, and other domination parameters of the graph.
Given a graph G, we consider γr(G), γ{R2}(G), γr2(G) and γR(G) as the weak Roman domination number, the Roman {2}-domination number, the 2-rainbow domination number and the Roman domination number of ...G, respectively.
It is known that γr(G)≤γ{R2}(G)≤γr2(G)≤γR(G) holds for any graph G. In connection with this, constructive characterizations of the trees T that satisfy the equalities above that are related with the weak Roman domination number are given in this work. That is, the trees T for which γr(T)=γ{R2}(T), γr(T)=γr2(T) and γr(T)=γR(T) are described.
Perfect Italian domination in trees Haynes, Teresa W.; Henning, Michael A.
Discrete Applied Mathematics,
05/2019, Letnik:
260
Journal Article
Recenzirano
Odprti dostop
A perfect Italian dominating function on a graph G is a function f:V(G)→{0,1,2} satisfying the condition that for every vertex u with f(u)=0, the total weight of f assigned to the neighbors of u is ...exactly two. The weight of a perfect Italian dominating function is the sum of the weights of the vertices. The perfect Italian domination number of G, denoted γIp(G), is the minimum weight of a perfect Italian dominating function of G. We show that if G is a tree on n≥3 vertices, then γIp(G)≤45n, and for each positive integer n≡0(mod5) there exists a tree of order n for which equality holds in the bound.
A subset $S \subseteq V(G)$ is said to be a perfect equitable isolate dominating set of a graph $G$ if it is both perfect equitable dominating set of $G$ and isolate dominating set of $G$. The ...minimum cardinality of a perfect equitable isolate dominating set is called perfect equitable isolate domination number of $G$ and is denoted by $\gamma_{pe0}(G)$. A perfect equitable isolate dominating set $S$ of $G$ is called $\gamma_{pe0}$-set of $G$. In this paper, the authors give characterizations of a perfect equitable isolate dominating set of some graphs and graphs obtained from the join and corona of two graphs. Furthermore, the perfect equitable isolate domination numbers of these graphs is determined, and the graphs with no perfect equitable isolate dominating sets are investigated.
Let G=(V,\ E) be a simple graph. A subset S of E(G) is a strong (weak) efficient edge dominating set of G if │Nse S│ = 1 for all e E(G)(│Nwe S│ = 1 for all e E(G)) where Ns(e) ={f / f E(G), ...f is adjacent to e & deg f ≥ deg e}(Nw(e) ={f / f E(G), f is adjacent to e & deg f ≤ deg e}) and Nse=Ns(e){e}(Nwe = Nw(e){e}). The minimum cardinality of a strong efficient edge dominating set of G (weak efficient edge dominating set of G) is called a strong efficient edge domination number of G and is denoted by {\gamma\prime}_{se}(G) ({\gamma^\prime}_{we}(G)).When a vertex is removed or an edge is added to the graph, the strong efficient edge domination number may or may not be changed. In this paper the change or unchanged of the strong efficient edge domination number of some standard graphs are determined, when a vertex is removed or an edge is added.
PDF
