Log in

Relevant bibliographies by topics / Roman domination / Journal articles

To see the other types of publications on this topic, follow the link: Roman domination.

Journal articles on the topic 'Roman domination'

Author: Grafiati

Published: 4 June 2021

Last updated: 21 February 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Roman domination.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

KUMAR, H. NARESH, and Y. B. VENKATAKRISHNAN. "Vertex-Edge Roman Domination." Kragujevac Journal of Mathematics 45, no. 5 (2021): 685–98. http://dx.doi.org/10.46793/kgjmat2105.685k.

Full text

Abstract:

A vertex-edge Roman dominating function (or just ve-RDF) of a graph G = (V,E) is a function f : V (G) →{0, 1, 2} such that for each edge e = uv either max{f(u),f(v)}≠0 or there exists a vertex w such that either wu ∈ E or wv ∈ E and f(w) = 2. The weight of a ve-RDF is the sum of its function values over all vertices. The vertex-edge Roman domination number of a graph G, denoted by γveR(G), is the minimum weight of a ve-RDF G. In this paper, we initiate a study of vertex-edge Roman dominaton. We ﬁrst show that determining the number γveR(G) is NP-complete even for bipartite graphs. Then we show that if T is a tree diﬀerent from a star with order n, l leaves and s support vertices, then γveR(T) ≥ (n − l − s + 3)∕2, and we characterize the trees attaining this lower bound. Finally, we provide a characterization of all trees with γveR(T) = 2γ′(T), where γ′(T) is the edge domination number of T.

APA, Harvard, Vancouver, ISO, and other styles

2

Entero, Giovannie, and Stephanie Espinola. "On the Global Distance Roman Domination of Some Graphs." European Journal of Pure and Applied Mathematics 16, no. 1 (January 29, 2023): 44–61. http://dx.doi.org/10.29020/nybg.ejpam.v16i1.4478.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

3

Li, Yong, Qiong Li, Jian He, Xinruan Fan, and Zhaoheng Ding. "On the Unique Response Roman Domination Numbers of Graphs." Journal of Computational and Theoretical Nanoscience 13, no. 10 (October 1, 2016): 7362–65. http://dx.doi.org/10.1166/jctn.2016.5727.

Full text

Abstract:

Let G be a graph with vertex set V(G). A function f: V(G) → {0, 1, 2} with the ordered partition (V0, V1, V2) of V(G), where Vi = {V∈V(G) | f(V) = i} for i = 0, 1, 2, is a Roman dominating function if x ∈ V0 implies |N(x)∩V2|≥ 1. It is a unique response Roman function if x ∈ V0 implies |N(x) ≥ V2|≤ 1 and x ∈ V1 ∪ V2 implies that |N(x) ∩ V2| = 0. A function f: V(G) → {0, 1, 2} is a unique response Roman dominating function if it is both a unique response Roman function and a Roman dominating function. The unique response Roman domination number, denoted by uR(G), of G is the minimum weight of a unique response Roman dominating function. In this paper we study the unique response Roman domination of graphs, and provide some graphs whose unique response Roman domination number equals to the independent Roman domination number.

APA, Harvard, Vancouver, ISO, and other styles

4

Chellali, Mustapha, Teresa Haynes, and Stephen Hedetniemi. "Lower bounds on the Roman and independent Roman domination numbers." Applicable Analysis and Discrete Mathematics 10, no. 1 (2016): 65–72. http://dx.doi.org/10.2298/aadm151112023c.

Full text

Abstract:

A Roman dominating function (RDF) on a graph G is a function f : V (G) ? {0,1,2} satisfying the condition that every vertex u with f(u) = 0 is adjacent to at least one vertex v of G for which f(v) = 2. The weight of a Roman dominating function is the sum f(V) = ?v?V f(v), and the minimum weight of a Roman dominating function f is the Roman domination number ?R(G). An RDF f is called an independent Roman dominating function (IRDF) if the set of vertices assigned positive values under f is independent. The independent Roman domination number iR(G) is the minimum weight of an IRDF on G. We show that for every nontrivial connected graph G with maximum degree ?, ?R(G)? ?+1/??(G) and iR(G) ? i(G) + ?(G)/?, where ?(G) and i(G) are, respectively, the domination and independent domination numbers of G. Moreover, we characterize the connected graphs attaining each lower bound. We give an additional lower bound for ?R(G) and compare our two new bounds on ?R(G) with some known lower bounds.

APA, Harvard, Vancouver, ISO, and other styles

5

Amjadi, J., S. Nazari-Moghaddam, and S. M. Sheikholeslami. "Global total Roman domination in graphs." Discrete Mathematics, Algorithms and Applications 09, no. 04 (August 2017): 1750050. http://dx.doi.org/10.1142/s1793830917500501.

Full text

Abstract:

A total Roman dominating function (TRDF) on a graph [Formula: see text] is a function [Formula: see text] satisfying the conditions (i) every vertex [Formula: see text] for which [Formula: see text] is adjacent at least one vertex [Formula: see text] for which [Formula: see text] and (ii) the subgraph of [Formula: see text] 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 [Formula: see text] is called a global total Roman dominating function (GTRDF) if [Formula: see text] is also a TRDF of the complement [Formula: see text] of [Formula: see text]. The global total Roman domination number of [Formula: see text] is the minimum weight of a GTRDF on [Formula: see text]. 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.

APA, Harvard, Vancouver, ISO, and other styles

6

Shao, Zehui, Doost Ali Mojdeh, and Lutz Volkmann. "Total Roman {3}-domination in Graphs." Symmetry 12, no. 2 (February 9, 2020): 268. http://dx.doi.org/10.3390/sym12020268.

Full text

Abstract:

For a graph G = ( V , E ) with vertex set V = V ( G ) and edge set E = E ( G ) , a Roman { 3 } -dominating function (R { 3 } -DF) is a function f : V ( G ) → { 0 , 1 , 2 , 3 } having the property that ∑ u ∈ N G ( v ) f ( u ) ≥ 3 , if f ( v ) = 0 , and ∑ u ∈ N G ( v ) f ( u ) ≥ 2 , if f ( v ) = 1 for any vertex v ∈ V ( G ) . The weight of a Roman { 3 } -dominating function f is the sum f ( V ) = ∑ v ∈ V ( G ) f ( v ) and the minimum weight of a Roman { 3 } -dominating function on G is the Roman { 3 } -domination number of G, denoted by γ { R 3 } ( G ) . Let G be a graph with no isolated vertices. The total Roman { 3 } -dominating function on G is an R { 3 } -DF f on G with the additional property that every vertex v ∈ V with f ( v ) ≠ 0 has a neighbor w with f ( w ) ≠ 0 . The minimum weight of a total Roman { 3 } -dominating function on G, is called the total Roman { 3 } -domination number denoted by γ t { R 3 } ( G ) . We initiate the study of total Roman { 3 } -domination and show its relationship to other domination parameters. We present an upper bound on the total Roman { 3 } -domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound. Finally, we investigate the complexity of total Roman { 3 } -domination for bipartite graphs.

APA, Harvard, Vancouver, ISO, and other styles

7

Martínez, Abel Cabrera, Iztok Peterin, and Ismael G. Yero. "Roman domination in direct product graphs and rooted product graphs." AIMS Mathematics 6, no. 10 (2021): 11084–96. http://dx.doi.org/10.3934/math.2021643.

Full text

Abstract:

<abstract><p>Let $ G $ be a graph with vertex set $ V(G) $. A function $ f:V(G)\rightarrow \{0, 1, 2\} $ is a Roman dominating function on $ G $ if every vertex $ v\in V(G) $ for which $ f(v) = 0 $ is adjacent to at least one vertex $ u\in V(G) $ such that $ f(u) = 2 $. The Roman domination number of $ G $ is the minimum weight $ \omega(f) = \sum_{x\in V(G)}f(x) $ among all Roman dominating functions $ f $ on $ G $. In this article we study the Roman domination number of direct product graphs and rooted product graphs. Specifically, we give several tight lower and upper bounds for the Roman domination number of direct product graphs involving some parameters of the factors, which include the domination, (total) Roman domination, and packing numbers among others. On the other hand, we prove that the Roman domination number of rooted product graphs can attain only three possible values, which depend on the order, the domination number, and the Roman domination number of the factors in the product. In addition, theoretical characterizations of the classes of rooted product graphs achieving each of these three possible values are given.</p></abstract>

APA, Harvard, Vancouver, ISO, and other styles

8

Chellali, Mustapha, and Nader Jafari Rad. "Trees with independent Roman domination number twice the independent domination number." Discrete Mathematics, Algorithms and Applications 07, no. 04 (December 2015): 1550048. http://dx.doi.org/10.1142/s1793830915500482.

Full text

Abstract:

A Roman dominating function (RDF) on a graph [Formula: see text] is a function [Formula: see text] satisfying the condition that every vertex [Formula: see text] for which [Formula: see text] is adjacent to at least one vertex [Formula: see text] for which [Formula: see text]. The weight of a RDF [Formula: see text] is the value [Formula: see text]. The Roman domination number, [Formula: see text], of [Formula: see text] is the minimum weight of a RDF on [Formula: see text]. An RDF [Formula: see text] is called an independent Roman dominating function (IRDF) if the set [Formula: see text] is an independent set. The independent Roman domination number, [Formula: see text], is the minimum weight of an IRDF on [Formula: see text]. In this paper, we study trees with independent Roman domination number twice their independent domination number, answering an open question.

APA, Harvard, Vancouver, ISO, and other styles

9

González, Yero, and Juan Rodríguez-Velázquez. "Roman domination in Cartesian product graphs and strong product graphs." Applicable Analysis and Discrete Mathematics 7, no. 2 (2013): 262–74. http://dx.doi.org/10.2298/aadm130813017g.

Full text

Abstract:

A map f : V ? {0, 1, 2} is a Roman dominating function for G if for every vertex v with f(v) = 0, there exists a vertex u, adjacent to v, with f(u) = 2. The weight of a Roman dominating function is f(V ) = ?u?v f(u). The minimum weight of a Roman dominating function on G is the Roman domination number of G. In this article we study the Roman domination number of Cartesian product graphs and strong product graphs.

APA, Harvard, Vancouver, ISO, and other styles

10

Paleta, Leonard Mijares, and Ferdinand Paler Jamil. "More on Perfect Roman Domination in Graphs." European Journal of Pure and Applied Mathematics 13, no. 3 (July 31, 2020): 529–48. http://dx.doi.org/10.29020/nybg.ejpam.v13i3.3763.

Full text

Abstract:

A perfect Roman dominating function on a graph G = (V (G), E(G)) is a function f : V (G) → {0, 1, 2} for which each u ∈ V (G) with f(u) = 0 is adjacent to exactly one vertex v ∈ V (G) with f(v) = 2. The weight of a perfect Roman dominating function f is the value ωG(f) = Pv∈V (G) f(v). The perfect Roman domination number of G is the minimum weight of a perfect Roman dominating function on G. In this paper, we study the perfect Roman domination numbers of graphs under some binary operation

APA, Harvard, Vancouver, ISO, and other styles

11

Ramezani, F., E. D. Rodríguez-Bazan, and J. A. Rodríguez-Velázquez. "On the roman domination number of generalized Sierpiński graphs." Filomat 31, no. 20 (2017): 6515–28. http://dx.doi.org/10.2298/fil1720515r.

Full text

Abstract:

A map f : V?(0,1,2) is a Roman dominating function on a graph G = (V,E) if for every vertex v ? V with f(v)=0, there exists a vertex u, adjacent to v, such that f(u)=2. The weight of a Roman dominating function is given by f(V)=?u?V f(u). The minimum weight among all Roman dominating functions on G is called the Roman domination number of G. In this article we study the Roman domination number of Generalized Sierpi?ski graphs S(G,t). More precisely, we obtain a general upper bound on the Roman domination number of S(G,t) and discuss the tightness of this bound. In particular, we focus on the cases in which the base graph G is a path, a cycle, a complete graph or a graph having exactly one universal vertex.

APA, Harvard, Vancouver, ISO, and other styles

12

Alhevaz, Abdollah, Mahsa Darkooti, Hadi Rahbani, and Yilun Shang. "Strong Equality of Perfect Roman and Weak Roman Domination in Trees." Mathematics 7, no. 10 (October 21, 2019): 997. http://dx.doi.org/10.3390/math7100997.

Full text

Abstract:

Let G = ( V , E ) be a graph and f : V ⟶ { 0 , 1 , 2 } be a function. Given a vertex u with f ( u ) = 0 , if all neighbors of u have zero weights, then u is called undefended with respect to f. Furthermore, if every vertex u with f ( u ) = 0 has a neighbor v with f ( v ) > 0 and the function f ′ : V ⟶ { 0 , 1 , 2 } with f ′ ( u ) = 1 , f ′ ( v ) = f ( v ) − 1 , f ′ ( w ) = f ( w ) if w ∈ V ∖ { u , v } has no undefended vertex, then f is called a weak Roman dominating function. Also, the function f is a perfect Roman dominating function if every vertex u with f ( u ) = 0 is adjacent to exactly one vertex v for which f ( v ) = 2 . Let the weight of f be w ( f ) = ∑ v ∈ V f ( v ) . The weak (resp., perfect) Roman domination number, denoted by γ r ( G ) (resp., γ R p ( G ) ), is the minimum weight of the weak (resp., perfect) Roman dominating function in G. In this paper, we characterize those trees where the perfect Roman domination number strongly equals the weak Roman domination number, in the sense that each weak Roman dominating function of minimum weight is, at the same time, perfect Roman dominating.

APA, Harvard, Vancouver, ISO, and other styles

13

Amjadi, J., and H. Sadeghi. "Triple Roman domination subdivision number in graphs." Computer Science Journal of Moldova 30, no. 1(88) (February 2022): 109–30. http://dx.doi.org/10.56415/csjm.v30.07.

Full text

Abstract:

For a graph $G=(V, E)$, a triple Roman domination function is a function $f: V(G)\longrightarrow\{0, 1, 2, 3, 4\}$ having the property that for any vertex $v\in V(G)$, if $f(v)<3$, then $f(\mbox{AN}[v])\geq|\mbox{AN}(v)|+3$, where $\mbox{AN}(v)=\{w\in N(v)\mid f(w)\geq1\}$ and $\mbox{AN}[v]=\mbox{AN}(v)\cup\{v\}$. The weight of a triple Roman dominating function $f$ is the value $\omega(f)=\sum_{v\in V(G)}f(v)$. The triple Roman domination number of $G$, denoted by $\gamma_{[3R]}(G)$, equals the minimum weight of a triple Roman dominating function on $G$. {\em The triple Roman domination subdivision number} $\mbox{sd}_{\gamma_{[3R]}}(G)$ of a graph $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 triple Roman domination number. In this paper, we first show that the decision problem associated with $\mbox{sd}_{\gamma_{[3R]}}(G)$ is NP-hard and then establish upper bounds on the triple Roman domination subdivision number for arbitrary graphs.

APA, Harvard, Vancouver, ISO, and other styles

14

Cabrera Martínez, A., C. García-Gómez, and J. A. Rodríguez-Velázquez. "Perfect Domination, Roman Domination and Perfect Roman Domination in Lexicographic Product Graphs." Fundamenta Informaticae 185, no. 3 (May 5, 2022): 201–20. http://dx.doi.org/10.3233/fi-222108.

Full text

Abstract:

The aim of this paper is to obtain closed formulas for the perfect domination number, the Roman domination number and the perfect Roman domination number of lexicographic product graphs. We show that these formulas can be obtained relatively easily for the case of the first two parameters. The picture is quite different when it concerns the perfect Roman domination number. In this case, we obtain general bounds and then we give sufficient and/or necessary conditions for the bounds to be achieved. We also discuss the case of perfect Roman graphs and we characterize the lexicographic product graphs where the perfect Roman domination number equals the Roman domination number.

APA, Harvard, Vancouver, ISO, and other styles

15

Yang, Hong, and Xiaoqing Zhou. "Some Properties of Double Roman Domination." Discrete Dynamics in Nature and Society 2020 (August 14, 2020): 1–5. http://dx.doi.org/10.1155/2020/6481092.

Full text

Abstract:

A double Roman dominating function on a graph G is a function f:VG⟶0,1,2,3 satisfying the conditions that every vertex u for which fu=0 is adjacent to at least one vertex v for which fv=3 or two vertices v1 and v2 for which fv1=fv2=2 and every vertex u for which fu=1 is adjacent to at least one vertex v for which fv≥2. The weight of a double Roman dominating function f is the value fV=∑u∈Vfu. The minimum weight of a double Roman dominating function on a graph G is called the double Roman domination numberγdRG of G. A graph with γdRG=3γG is called a double Roman graph. In this paper, we study properties of double Roman domination in graphs. Moreover, we find a class of double Roman graphs and give characterizations of trees with γdRT=γRT+k for k=1,2.

APA, Harvard, Vancouver, ISO, and other styles

16

KUMAR, M. KAMAL, and L. SUDERSHAN REDDY. "INVERSE ROMAN DOMINATION IN GRAPHS." Discrete Mathematics, Algorithms and Applications 05, no. 03 (September 2013): 1350011. http://dx.doi.org/10.1142/s1793830913500110.

Full text

Abstract:

Motivated by the article in Scientific American [7], Michael A Henning and Stephen T Hedetniemi explored the strategy of defending the Roman Empire. Cockayne defined Roman dominating function (RDF) on a Graph G = (V, E) to be a function f : V → {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. For a real valued function f : V → R the weight of f is w(f) = ∑v∈V f(v). The Roman domination number (RDN) denoted by γR(G) is the minimum weight among all RDF in G. If V – D contains a roman dominating function f1 : V → {0, 1, 2}. "D" is the set of vertices v for which f(v) > 0. Then f1 is called Inverse Roman Dominating function (IRDF) on a graph G w.r.t. f. The inverse roman domination number (IRDN) denoted by [Formula: see text] is the minimum weight among all IRDF in G. In this paper we find few results of IRDN.

APA, Harvard, Vancouver, ISO, and other styles

17

Shirkol, Shailaja S., Pavitra P. Kumbargoudra, and Meenal M. Kaliwal. "DOUBLE ROMAN DOMINATION NUMBER OF MIDDLE GRAPH." South East Asian J. of Mathematics and Mathematical Sciences 18, no. 03 (December 30, 2022): 369–80. http://dx.doi.org/10.56827/seajmms.2022.1803.31.

Full text

Abstract:

For any graph G(V, E), a function f : V (G) 0, 1, 2, 3 is called Double Roman dominating function (DRDF) if the following properties holds, If f (v) = 0, then there exist two vertices v1, v2 ∈ N (v) for which f (v1) = f (v2) = 2 or there exist one vertex u ∈ N (v) for which f (u) = 3.∈ If f (v) = 1, then there exist one vertex u N (v) for which f (u) = 2 or Σ f (u) = 3. The weight of DRDF is the value w(f ) = v∈V (G) f (v). The minimum weight among all double Roman dominating function is called double Roman domination number and is denoted by γdR(G). In this article we initiated research on double Roman domination number for middle graphs. We established lower and upper bounds and also we characterize the double Roman domination number of middle graphs. Later we calculated numerical value of double Roman domination number of middle graph of path, cycle, star, double star and friendship graphs.

APA, Harvard, Vancouver, ISO, and other styles

18

Wu, Pu, Zepeng Li, Zehui Shao, and Seyed Mahmoud Sheikholeslami. "Trees with equal Roman {2}-domination number and independent Roman {2}-domination number." RAIRO - Operations Research 53, no. 2 (March 6, 2019): 389–400. http://dx.doi.org/10.1051/ro/2018116.

Full text

Abstract:

A Roman {2}-dominating function (R{2}DF) on a graph G =(V, E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to either at least one vertex v with f(v) = 2 or two vertices v1, v2 with f(v1) = f(v2) = 1. The weight of an R{2}DF f is the value w(f) = ∑u∈Vf(u). The minimum weight of an R{2}DF on a graph G is called the Roman {2}-domination number γ{R2}(G) of G. An R{2}DF f is called an independent Roman {2}-dominating function (IR{2}DF) if the set of vertices with positive weight under f is independent. The minimum weight of an IR{2}DF on a graph G is called the independent Roman {2}-domination number i{R2}(G) of G. In this paper, we answer two questions posed by Rahmouni and Chellali.

APA, Harvard, Vancouver, ISO, and other styles

19

Almerich-Chulia, Ana, Abel Cabrera Martínez, Frank Angel Hernández Mira, and Pedro Martin-Concepcion. "From Total Roman Domination in Lexicographic Product Graphs to Strongly Total Roman Domination in Graphs." Symmetry 13, no. 7 (July 16, 2021): 1282. http://dx.doi.org/10.3390/sym13071282.

Full text

Abstract:

Let G be a graph with no isolated vertex and let N(v) be the open neighbourhood of v∈V(G). Let f:V(G)→{0,1,2} be a function and Vi={v∈V(G):f(v)=i} for every i∈{0,1,2}. We say that f is a strongly total Roman dominating function on G if the subgraph induced by V1∪V2 has no isolated vertex and N(v)∩V2≠∅ for every v∈V(G)\V2. The strongly total Roman domination number of G, denoted by γtRs(G), is defined as the minimum weight ω(f)=∑x∈V(G)f(x) among all strongly total Roman dominating functions f on G. This paper is devoted to the study of the strongly total Roman domination number of a graph and it is a contribution to the Special Issue “Theoretical Computer Science and Discrete Mathematics” of Symmetry. In particular, we show that the theory of strongly total Roman domination is an appropriate framework for investigating the total Roman domination number of lexicographic product graphs. We also obtain tight bounds on this parameter and provide closed formulas for some product graphs. Finally and as a consequence of the study, we prove that the problem of computing γtRs(G) is NP-hard.

APA, Harvard, Vancouver, ISO, and other styles

20

Shao, Zehui, Rija Erveš, Huiqin Jiang, Aljoša Peperko, Pu Wu, and Janez Žerovnik. "Double Roman Graphs in P(3k, k)." Mathematics 9, no. 4 (February 8, 2021): 336. http://dx.doi.org/10.3390/math9040336.

Full text

Abstract:

A double Roman dominating function on a graph G=(V,E) is a function f:V→{0,1,2,3} with the properties that if f(u)=0, then vertex u is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and if f(u)=1, then vertex u is adjacent to at least one vertex assigned 2 or 3. The weight of f equals w(f)=∑v∈Vf(v). The double Roman domination number γdR(G) of a graph G is the minimum weight of a double Roman dominating function of G. A graph is said to be double Roman if γdR(G)=3γ(G), where γ(G) is the domination number of G. We obtain the sharp lower bound of the double Roman domination number of generalized Petersen graphs P(3k,k), and we construct solutions providing the upper bounds, which gives exact values of the double Roman domination number for all generalized Petersen graphs P(3k,k). This implies that P(3k,k) is a double Roman graph if and only if either k≡0 (mod 3) or k∈{1,4}.

APA, Harvard, Vancouver, ISO, and other styles

21

Cabrera Martínez, Abel, Luis P. Montejano, and Juan A. Rodríguez-Velázquez. "Total Weak Roman Domination in Graphs." Symmetry 11, no. 6 (June 24, 2019): 831. http://dx.doi.org/10.3390/sym11060831.

Full text

Abstract:

Given a graph G = ( V , E ) , a function f : V → { 0 , 1 , 2 , ⋯ } is said to be a total dominating function if ∑ u ∈ N ( v ) f ( u ) > 0 for every v ∈ V , where N ( v ) denotes the open neighbourhood of v. Let V i = { x ∈ V : f ( x ) = i } . We say that a function f : V → { 0 , 1 , 2 } is a total weak Roman dominating function if f is a total dominating function and for every vertex v ∈ V 0 there exists u ∈ N ( v ) ∩ ( V 1 ∪ V 2 ) such that the function f ′ , defined by f ′ ( v ) = 1 , f ′ ( u ) = f ( u ) - 1 and f ′ ( x ) = f ( x ) whenever x ∈ V ∖ { u , v } , is a total dominating function as well. The weight of a function f is defined to be w ( f ) = ∑ v ∈ V f ( v ) . In this article, we introduce the study of the total weak Roman domination number of a graph G, denoted by γ t r ( G ) , which is defined to be the minimum weight among all total weak Roman dominating functions on G. We show the close relationship that exists between this novel parameter and other domination parameters of a graph. Furthermore, we obtain general bounds on γ t r ( G ) and, for some particular families of graphs, we obtain closed formulae. Finally, we show that the problem of computing the total weak Roman domination number of a graph is NP-hard.

APA, Harvard, Vancouver, ISO, and other styles

22

Mojdeh, Doost Ali, and Lutz Volkmann. "Roman {3}-domination (double Italian domination)." Discrete Applied Mathematics 283 (September 2020): 555–64. http://dx.doi.org/10.1016/j.dam.2020.02.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Chellali, Mustapha, Teresa W. Haynes, Stephen T. Hedetniemi, and Alice A. McRae. "Roman {2}-domination." Discrete Applied Mathematics 204 (May 2016): 22–28. http://dx.doi.org/10.1016/j.dam.2015.11.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Beeler, Robert A., Teresa W. Haynes, and Stephen T. Hedetniemi. "Double Roman domination." Discrete Applied Mathematics 211 (October 2016): 23–29. http://dx.doi.org/10.1016/j.dam.2016.03.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Kumar, H. Naresh, and Y. B. Venkatakrishnan. "Trees with vertex-edge roman domination number twice the domination number minus one." Proyecciones (Antofagasta) 39, no. 6 (December 1, 2020): 1381–92. http://dx.doi.org/10.22199/issn.0717-6279-2020-06-0084.

Full text

Abstract:

A vertex-edge Roman dominating function (or just ve-RDF) of a graph G = (V, E) is a function f : V (G) → {0, 1, 2} such that for each edge e = uv either max{f (u), f (v)} ≠ 0 or there exists a vertex w such that either wu ∈ E or wv ∈ E and f (w) = 2. The weight of a ve-RDF is the sum of its function values over all vertices. The vertex-edge Roman domination number of a graph G, denoted by γveR(G), is the minimum weight of a ve-RDF G. We characterize trees with vertexedge roman domination number equal to twice domination number minus one.

APA, Harvard, Vancouver, ISO, and other styles

26

Martínez, Abel Cabrera, Suitberto Cabrera García, Andrés Carrión García, and Angela María Grisales del Rio. "On the Outer-Independent Roman Domination in Graphs." Symmetry 12, no. 11 (November 9, 2020): 1846. http://dx.doi.org/10.3390/sym12111846.

Full text

Abstract:

Let G be a graph with no isolated vertex and f:V(G)→{0,1,2} a function. Let Vi={v∈V(G):f(v)=i} for every i∈{0,1,2}. The function f is an outer-independent Roman dominating function on G if V0 is an independent set and every vertex in V0 is adjacent to at least one vertex in V2. The minimum weight ω(f)=∑v∈V(G)f(v) among all outer-independent Roman dominating functions f on G is the outer-independent Roman domination number of G. This paper is devoted to the study of the outer-independent Roman domination number of a graph, and it is a contribution to the special issue “Theoretical Computer Science and Discrete Mathematics” of Symmetry. In particular, we obtain new tight bounds for this parameter, and some of them improve some well-known results. We also provide closed formulas for the outer-independent Roman domination number of rooted product graphs.

APA, Harvard, Vancouver, ISO, and other styles

27

Nazari-Moghaddam, S., and L. Volkmann. "Critical concept for double Roman domination in graphs." Discrete Mathematics, Algorithms and Applications 12, no. 02 (February 28, 2020): 2050020. http://dx.doi.org/10.1142/s1793830920500202.

Full text

Abstract:

A double Roman dominating function (DRDF) on a graph [Formula: see text] is a function [Formula: see text] such that (i) every vertex [Formula: see text] with [Formula: see text] is adjacent to at least two vertices assigned a [Formula: see text] or to at least one vertex assigned a [Formula: see text] and (ii) every vertex [Formula: see text] with [Formula: see text] is adjacent to at least one vertex [Formula: see text] with [Formula: see text] The weight of a DRDF is the sum of its function values over all vertices. The double Roman domination number [Formula: see text] equals the minimum weight of a DRDF on [Formula: see text] The concept of criticality with respect to various operations on graphs has been studied for several domination parameters. In this paper, we study the concept of criticality for double Roman domination in graphs. In addition, we characterize double Roman domination edge super critical graphs and we will give several characterizations for double Roman domination vertex (edge) critical graphs.

APA, Harvard, Vancouver, ISO, and other styles

28

Cabrera Martínez, Abel, Suitberto Cabrera García, Andrés Carrión García, and Frank A. Hernández Mira. "Total Roman Domination Number of Rooted Product Graphs." Mathematics 8, no. 10 (October 20, 2020): 1850. http://dx.doi.org/10.3390/math8101850.

Full text

Abstract:

Let G be a graph with no isolated vertex and f:V(G)→{0,1,2} a function. If f satisfies that every vertex in the set {v∈V(G):f(v)=0} is adjacent to at least one vertex in the set {v∈V(G):f(v)=2}, and if the subgraph induced by the set {v∈V(G):f(v)≥1} has no isolated vertex, then we say that f is a total Roman dominating function on G. The minimum weight ω(f)=∑v∈V(G)f(v) among all total Roman dominating functions f on G is the total Roman domination number of G. In this article we study this parameter for the rooted product graphs. Specifically, we obtain closed formulas and tight bounds for the total Roman domination number of rooted product graphs in terms of domination invariants of the factor graphs involved in this product.

APA, Harvard, Vancouver, ISO, and other styles

29

Shao, Zehui, Saeed Kosari, Hadi Rahbani, Mehdi Sharifzadeh, and Seyed Mahmoud Sheikholeslami. "Strong equality of Roman and perfect Roman Domination in trees." RAIRO - Operations Research 56, no. 1 (January 2022): 381–94. http://dx.doi.org/10.1051/ro/2022005.

Full text

Abstract:

A Roman dominating function (RD-function) on a graph G = (V, E) is a function f : V → {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. An Roman dominating function f in a graph G is perfect Roman dominating function (PRD-function) if every vertex u with f(u) = 0 is adjacent to exactly one vertex v for which f(v) = 2. The (perfect) Roman domination number γR(G) (γpR(G)) is the minimum weight of an (perfect) Roman dominating function on G. We say that γpR(G) strongly equals γR(G), denoted by γpR(G) ≡ γR(G), if every RD-function on G of minimum weight is a PRD-function. In this paper we show that for a given graph G, it is NP-hard to decide whether γpR(G) = γR(G) and also we provide a constructive characterization of trees T with γpR(T) ≡ γR(T).

APA, Harvard, Vancouver, ISO, and other styles

30

Martínez, Abel Cabrera, Dorota Kuziak, Iztok Peterin, and Ismael G. Yero. "Dominating the Direct Product of Two Graphs through Total Roman Strategies." Mathematics 8, no. 9 (August 27, 2020): 1438. http://dx.doi.org/10.3390/math8091438.

Full text

Abstract:

Given a graph G without isolated vertices, a total Roman dominating function for G is a function f:V(G)→{0,1,2} such that every vertex u with f(u)=0 is adjacent to a vertex v with f(v)=2, and the set of vertices with positive labels induces a graph of minimum degree at least one. The total Roman domination number γtR(G) of G is the smallest possible value of ∑v∈V(G)f(v) among all total Roman dominating functions f. The total Roman domination number of the direct product G×H of the graphs G and H is studied in this work. Specifically, several relationships, in the shape of upper and lower bounds, between γtR(G×H) and some classical domination parameters for the factors are given. Characterizations of the direct product graphs G×H achieving small values (≤7) for γtR(G×H) are presented, and exact values for γtR(G×H) are deduced, while considering various specific direct product classes.

APA, Harvard, Vancouver, ISO, and other styles

31

Mahmoodi, A. "On the signed strong Roman domination number of graphs." Discrete Mathematics, Algorithms and Applications 12, no. 02 (March 17, 2020): 2050028. http://dx.doi.org/10.1142/s1793830920500287.

Full text

Abstract:

Let [Formula: see text] be a finite and simple graph of order [Formula: see text] and maximum degree [Formula: see text]. A signed strong Roman dominating function on a graph [Formula: see text] is a function [Formula: see text] satisfying the conditions that (i) for every vertex [Formula: see text] of [Formula: see text], [Formula: see text], where [Formula: see text] is the closed neighborhood of [Formula: see text] and (ii) every vertex [Formula: see text] for which [Formula: see text] is adjacent to at least one vertex [Formula: see text] for which [Formula: see text], where [Formula: see text]. The minimum of the values [Formula: see text], taken over all signed strong Roman dominating functions [Formula: see text] of [Formula: see text], is called the signed strong Roman domination number of [Formula: see text] and is denoted by [Formula: see text]. In this paper, we continue the study signed strong Roman domination number of a graph and give several bounds for this parameter. Then, among other results, we determine the signed strong Roman domination number of special classes of graphs.

APA, Harvard, Vancouver, ISO, and other styles

32

Poureidi, Abolfazl. "A linear algorithm for double Roman domination of proper interval graphs." Discrete Mathematics, Algorithms and Applications 12, no. 01 (December 30, 2019): 2050011. http://dx.doi.org/10.1142/s1793830920500111.

Full text

Abstract:

A function [Formula: see text] is a double Roman dominating function on a graph [Formula: see text] if for every vertex [Formula: see text] with [Formula: see text] either there is a vertex [Formula: see text] with [Formula: see text] or there are distinct vertices [Formula: see text] with [Formula: see text] and for every vertex [Formula: see text] with [Formula: see text] there is a vertex [Formula: see text] with [Formula: see text]. The weight of a double Roman dominating function [Formula: see text] on [Formula: see text] is the value [Formula: see text]. The minimum weight of a double Roman dominating function on [Formula: see text] is called the double Roman domination number of [Formula: see text]. In this paper, we give an algorithm to compute the double Roman domination number of a given proper interval graph [Formula: see text] in [Formula: see text] time.

APA, Harvard, Vancouver, ISO, and other styles

33

Henning, Michael, and William Klostermeyer. "Perfect roman domination in regular graphs." Applicable Analysis and Discrete Mathematics 12, no. 1 (2018): 143–52. http://dx.doi.org/10.2298/aadm1801143h.

Full text

Abstract:

A perfect Roman dominating function on a graph G is a function f : V (G) ? {0,1,2} satisfying the condition that every vertex u with f(u) = 0 is adjacent to exactly one vertex v for which f(v) = 2. The weight of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted ?pR(G), is the minimum weight of a perfect Roman dominating function in G. We show that if G is a cubic graph on n vertices, then ?pR(G) ? 3/4n, and this bound is best possible. Further, we show that if G is a k-regular graph on n vertices with k at least 4, then ?pR(G) ? (k2+k+3/k2+3k+1)n.

APA, Harvard, Vancouver, ISO, and other styles

34

Kou, Zheng, Saeed Kosari, Guoliang Hao, Jafar Amjadi, and Nesa Khalili. "Quadruple Roman Domination in Trees." Symmetry 13, no. 8 (July 22, 2021): 1318. http://dx.doi.org/10.3390/sym13081318.

Full text

Abstract:

This paper is devoted to the study of the quadruple Roman domination in trees, and it is a contribution to the Special Issue “Theoretical computer science and discrete mathematics” of Symmetry. For any positive integer k, a [k]-Roman dominating function ([k]-RDF) of a simple graph G is a function from the vertex set V of G to the set {0,1,2,…,k+1} if for any vertex u∈V with f(u)<k, ∑x∈N(u)∪{u}f(x)≥|{x∈N(u):f(x)≥1}|+k, where N(u) is the open neighborhood of u. The weight of a [k]-RDF is the value Σv∈Vf(v). The minimum weight of a [k]-RDF is called the [k]-Roman domination number γ[kR](G) of G. In this paper, we establish sharp upper and lower bounds on γ[4R](T) for nontrivial trees T and characterize extremal trees.

APA, Harvard, Vancouver, ISO, and other styles

35

Sheikholeslami, Seyed Mahmoud, Rana Khoeilar, and Leila Asgharsharghi. "Signed strong Roman domination in graphs." Tamkang Journal of Mathematics 48, no. 2 (June 30, 2017): 135–47. http://dx.doi.org/10.5556/j.tkjm.48.2017.2240.

Full text

Abstract:

Let $G=(V,E)$ be a finite and simple graph of order $n$ and maximum degree $\Delta$. A signed strong Roman dominating function (abbreviated SStRDF) on a graph $G$ is a function $f:V\to \{-1,1,2,\ldots,\lceil\frac{\Delta}{2}\rceil+1\}$ satisfying the conditions that (i) for every vertex $v$ of $G$, $\sum_{u\in N[v]} f(u)\ge 1$, where $N[v]$ is the closed neighborhood of $v$ and (ii) every vertex $v$ for which $f(v)=-1$ is adjacent to at least one vertex $u$ for which $f(u)\ge 1+\lceil\frac{1}{2}|N(u)\cap V_{-1}|\rceil$, where $V_{-1}=\{v\in V \mid f(v)=-1\}$. The minimum of the values $\sum_{v\in V} f(v)$, taken over all signed strong Roman dominating functions $f$ of $G$, is called the signed strong Roman domination number of $G$ and is denoted by $\gamma_{ssR}(G)$. In this paper we initiate the study of the signed strong Roman domination in graphs and present some (sharp) bounds for this parameter.

APA, Harvard, Vancouver, ISO, and other styles

36

Alvarado, Jose D., Simone Dantas, and Dieter Rautenbach. "Relating 2-rainbow domination to Roman domination." Discussiones Mathematicae Graph Theory 37, no. 4 (2017): 953. http://dx.doi.org/10.7151/dmgt.1956.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Alvarado, José D., Simone Dantas, and Dieter Rautenbach. "Averaging 2-rainbow domination and Roman domination." Discrete Applied Mathematics 205 (May 2016): 202–7. http://dx.doi.org/10.1016/j.dam.2016.01.021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Martínez, Abel Cabrera, Juan C. Hernández-Gómez, and José M. Sigarreta. "On the Quasi-Total Roman Domination Number of Graphs." Mathematics 9, no. 21 (November 6, 2021): 2823. http://dx.doi.org/10.3390/math9212823.

Full text

Abstract:

Domination theory is a well-established topic in graph theory, as well as one of the most active research areas. Interest in this area is partly explained by its diversity of applications to real-world problems, such as facility location problems, computer and social networks, monitoring communication, coding theory, and algorithm design, among others. In the last two decades, the functions defined on graphs have attracted the attention of several researchers. The Roman-dominating functions and their variants are one of the main attractions. This paper is a contribution to the Roman domination theory in graphs. In particular, we provide some interesting properties and relationships between one of its variants: the quasi-total Roman domination in graphs.

APA, Harvard, Vancouver, ISO, and other styles

39

Meiyanathan, M., and K. Anitha. "Domination, Edge Domination and Roman Domination in Human Chain Graph." Journal of Physics: Conference Series 1724, no. 1 (January 1, 2021): 012023. http://dx.doi.org/10.1088/1742-6596/1724/1/012023.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Chellali, Mustapha, Teresa W. Haynes, and Stephen T. Hedetniemi. "Roman and Total Domination." Quaestiones Mathematicae 38, no. 6 (December 4, 2015): 749–57. http://dx.doi.org/10.2989/16073606.2015.1015647.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Chellali, Mustapha, Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Alice A. McRae. "A Roman Domination Chain." Graphs and Combinatorics 32, no. 1 (March 26, 2015): 79–92. http://dx.doi.org/10.1007/s00373-015-1566-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Cockayne, Ernie J., Paul A. Dreyer, Sandra M. Hedetniemi, and Stephen T. Hedetniemi. "Roman domination in graphs." Discrete Mathematics 278, no. 1-3 (March 2004): 11–22. http://dx.doi.org/10.1016/j.disc.2003.06.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

V., Anu, and Aparna Lakshmanan S. "Double Roman domination number." Discrete Applied Mathematics 244 (July 2018): 198–204. http://dx.doi.org/10.1016/j.dam.2018.03.026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Bouchou, Ahmed, Mostafa Blidia, and Mustapha Chellali. "Relations between the Roman k-domination and Roman domination numbers in graphs." Discrete Mathematics, Algorithms and Applications 06, no. 03 (June 16, 2014): 1450045. http://dx.doi.org/10.1142/s1793830914500451.

Full text

Abstract:

Let G = (V, E) be a graph and let k be a positive integer. A Roman k-dominating function ( R k-DF) on G is a function f : V(G) → {0, 1, 2} such that every vertex u for which f(u) = 0 is adjacent to at least k vertices v1, v2, …, vk with f(vi) = 2 for i = 1, 2, …, k. The weight of an R k-DF is the value f(V(G)) = ∑u∈V(G) f(u) and the minimum weight of an R k-DF on G is called the Roman k-domination number γkR(G) of G. In this paper, we present relations between γkR(G) and γR(G). Moreover, we give characterizations of some classes of graphs attaining equality in these relations. Finally, we establish a relation between γkR(G) and γR(G) for {K1,3, K1,3+e}-free graphs and we characterize all such graphs G with γkR(G) = γR(G)+t, where [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

45

Padamutham, Chakradhar, and Venkata Subba Reddy Palagiri. "Complexity of Roman {2}-domination and the double Roman domination in graphs." AKCE International Journal of Graphs and Combinatorics 17, no. 3 (May 4, 2020): 1081–86. http://dx.doi.org/10.1016/j.akcej.2020.01.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Rupnik Poklukar, Darja, and Janez Žerovnik. "Double Roman Domination in Generalized Petersen Graphs P(ck, k)." Symmetry 14, no. 6 (May 29, 2022): 1121. http://dx.doi.org/10.3390/sym14061121.

Full text

Abstract:

A double Roman dominating function on a graph G=(V,E) is a function f:V→{0,1,2,3}, satisfying the condition that every vertex u for which f(u)=1 is adjacent to at least one vertex assigned 2 or 3, and every vertex u with f(u)=0 is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2. The weight of f equals the sum w(f)=∑v∈Vf(v). The minimum weight of a double Roman dominating function of G is called the double Roman domination number γdR(G) of a graph G. We obtain tight bounds and in some cases closed expressions for the double Roman domination number of generalized Petersen graphs P(ck,k). In short, we prove that γdR(P(ck,k))=32ck+ε, where limc→∞,k→∞εck=0.

APA, Harvard, Vancouver, ISO, and other styles

47

Zaman, Zulfiqar, M. Kamal Kumar, and Saad Salman Ahmad. "Roman and inverse Roman domination in graphs." Notes on Number Theory and Discrete Mathematics 24, no. 3 (October 9, 2018): 142–50. http://dx.doi.org/10.7546/nntdm.2018.24.3.142-150.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Rupnik Poklukar, Darja, and Janez Žerovnik. "On the Double Roman Domination in Generalized Petersen Graphs P(5k,k)." Mathematics 10, no. 1 (January 1, 2022): 119. http://dx.doi.org/10.3390/math10010119.

Full text

Abstract:

A double Roman dominating function on a graph G=(V,E) is a function f:V→{0,1,2,3} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and every vertex u with f(u)=1 is adjacent to at least one vertex assigned 2 or 3. The weight of f equals w(f)=∑v∈Vf(v). The double Roman domination number γdR(G) of a graph G equals the minimum weight of a double Roman dominating function of G. We obtain closed expressions for the double Roman domination number of generalized Petersen graphs P(5k,k). It is proven that γdR(P(5k,k))=8k for k≡2,3mod5 and 8k≤γdR(P(5k,k))≤8k+2 for k≡0,1,4mod5. We also improve the upper bounds for generalized Petersen graphs P(20k,k).

APA, Harvard, Vancouver, ISO, and other styles

49

Shao, Zehui, Saeed Kosari, Mustapha Chellali, Seyed Mahmoud Sheikholeslami, and Marzieh Soroudi. "On a Relation between the Perfect Roman Domination and Perfect Domination Numbers of a Tree." Mathematics 8, no. 6 (June 12, 2020): 966. http://dx.doi.org/10.3390/math8060966.

Full text

Abstract:

A dominating set in a graph G is a set of vertices S ⊆ V ( G ) such that any vertex of V − S is adjacent to at least one vertex of S . A dominating set S of G is said to be a perfect dominating set if each vertex in V − S is adjacent to exactly one vertex in S. The minimum cardinality of a perfect dominating set is the perfect domination number γ p ( G ) . A function f : V ( G ) → { 0 , 1 , 2 } is a perfect Roman dominating function (PRDF) on G if every vertex u ∈ V for which f ( u ) = 0 is adjacent to exactly one vertex v for which f ( v ) = 2 . The weight of a PRDF is the sum of its function values over all vertices, and the minimum weight of a PRDF of G is the perfect Roman domination number γ R p ( G ) . In this paper, we prove that for any nontrivial tree T, γ R p ( T ) ≥ γ p ( T ) + 1 and we characterize all trees attaining this bound.

APA, Harvard, Vancouver, ISO, and other styles

50

Chellali, Mustapha, and Nader Jafari Rad. "Strong equality between the Roman domination and independent Roman domination numbers in trees." Discussiones Mathematicae Graph Theory 33, no. 2 (2013): 337. http://dx.doi.org/10.7151/dmgt.1669.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!