-
Total Roman {2}-Dominating functions in Graphs
Authors:
H. Abdollahzadeh Ahangar,
M. Chellali,
S. M. Sheikholeslami,
J. C. Valenzuela-Tripodoro
Abstract:
A Roman $\{2\}$-dominating function (R2F) is a function $f:V\rightarrow \{0,1,2\}$ with the property that for every vertex $v\in V$ with $f(v)=0$ there is a neighbor $u$ of $v$ with $f(u)=2$, or there are two neighbors $x,y$ of $v$ with $f(x)=f(y)=1$. A total Roman $\{2\}$-dominating function (TR2DF) is an R2F $f$ such that the set of vertices with $f(v)>0$ induce a subgraph with no isolated verti…
▽ More
A Roman $\{2\}$-dominating function (R2F) is a function $f:V\rightarrow \{0,1,2\}$ with the property that for every vertex $v\in V$ with $f(v)=0$ there is a neighbor $u$ of $v$ with $f(u)=2$, or there are two neighbors $x,y$ of $v$ with $f(x)=f(y)=1$. A total Roman $\{2\}$-dominating function (TR2DF) is an R2F $f$ such that the set of vertices with $f(v)>0$ induce a subgraph with no isolated vertices. The weight of a TR2DF is the sum of its function values over all vertices, and the minimum weight of a TR2DF of $G$ is the total Roman $\{2\}$-domination number $γ_{tR2}(G).$ In this paper, we initiate the study of total Roman $\{2\}$-dominating functions, where properties are established. Moreover, we present various bounds on the total Roman $\{2\}$-domination number. We also show that the decision problem associated with $γ_{tR2}(G)$ is NP-complete for bipartite and chordal graphs. {Moreover, we show that it is possible to compute this parameter in linear time for bounded clique-width graphs (including tres).}
△ Less
Submitted 12 February, 2024;
originally announced February 2024.
-
On the outer independent total double Roman dominating functions
Authors:
H. Abdolahzadeh Ahangar,
M. Chellali,
S. M. Sheikholeslami,
J. C. Valenzuela-Tripodoro
Abstract:
Let $\{0,1,\dots, t\}$ be abbreviated by $[t].$ A double Roman dominating function (DRDF) on a graph $Γ=(V,E)$ is a map $l:V\rightarrow [3]$ satisfying \textrm{(i)} if $l(r)=0$ then there must be at least two neighbors labeled 2 under $l$ or a neighbor $r'$ with $l(r')=3$; and \textrm{(ii)} if $l(r)=1$ then $r$ must be adjacent to a vertex $r'$ such that $l(r')\geq2$. A DRDF is an outer-independen…
▽ More
Let $\{0,1,\dots, t\}$ be abbreviated by $[t].$ A double Roman dominating function (DRDF) on a graph $Γ=(V,E)$ is a map $l:V\rightarrow [3]$ satisfying \textrm{(i)} if $l(r)=0$ then there must be at least two neighbors labeled 2 under $l$ or a neighbor $r'$ with $l(r')=3$; and \textrm{(ii)} if $l(r)=1$ then $r$ must be adjacent to a vertex $r'$ such that $l(r')\geq2$. A DRDF is an outer-independent total double Roman dominating function (OITDRDF) on $Γ$ if the set of vertices labeled $0$ induces an edgeless subgraph and the subgraph induced by the vertices with a non-zero label has no isolated vertices. The weight of an OITDRDF is the sum of its map values over all vertices, and the outer independent total Roman dominating number $γ_{tdR}^{oi}(Γ)$ is the minimum weight of an OITDRDF on $Γ$. First, we prove that the problem of determining $γ_{tdR}^{oi}(Γ)$ is NP-complete for bipartite and chordal graphs, after that, we prove that it is solvable in linear time when we are restricting to bounded clique-width graphs. Moreover, we present some tight bounds on $γ_{tdR}^{oi}(Γ)$ as well as the exact values for several graph families.
△ Less
Submitted 10 February, 2024;
originally announced February 2024.
-
Maximal double Roman domination in graphs
Authors:
H. Abdollahzadeh Ahangar,
M. Chellali,
S. M. Sheikholeslami,
J. C. Valenzuela-Tripodoro
Abstract:
A maximal double Roman dominating function (MDRDF) on a graph $G=(V,E)$ is a function $f:V(G)\rightarrow \{0,1,2,3\}$ such that \textrm{(i) }every vertex $v$ with $f(v)=0$ is adjacent to least two vertices { assigned $2$ or to at least one vertex assigned $3,$} \textrm{(ii) }every vertex $v$ with $f(v)=1$ is adjacent to at least one { vertex assigned $2$ or $3$} and \textrm{(iii) }the set…
▽ More
A maximal double Roman dominating function (MDRDF) on a graph $G=(V,E)$ is a function $f:V(G)\rightarrow \{0,1,2,3\}$ such that \textrm{(i) }every vertex $v$ with $f(v)=0$ is adjacent to least two vertices { assigned $2$ or to at least one vertex assigned $3,$} \textrm{(ii) }every vertex $v$ with $f(v)=1$ is adjacent to at least one { vertex assigned $2$ or $3$} and \textrm{(iii) }the set $\{w\in V|~f(w)=0\}$ is not a dominating set of $G $. The weight of a MDRDF is the sum of its function values over all vertices, and the maximal double Roman domination number $γ_{dR}^{m}(G) $ is the minimum weight of an MDRDF on $G$. {In this paper, we initiate the study of maximal double Roman domination. We first show that the problem of determining }$γ_{dR}^{m}(G)$ {is NP-complete for bipartite, chordal and planar graphs. But it is solvable in linear time for bounded clique-width graphs including trees, cographs and distance-hereditary graphs. Moreover, we establish various relationships relating }$γ_{dR}^{m}(G)$ to some domination parameters. {For the class of trees, we show that for every tree }$T$ {of order }$n\geq 4,$ $γ_{dR}^{m}(T)\leq \frac{5}{4}n$ {and we characterize all trees attaining the bound. Finally, the exact values of }$γ_{dR}^{m}(G) $ {are given for paths and cycles.
△ Less
Submitted 10 February, 2024;
originally announced February 2024.
-
Triple Roman Domination in Graphs
Authors:
Hossein Abdollahzadeh Ahangar,
M. Pilar Alvarez,
Mustapha Chellali,
Seyed Mahmoud Sheikholeslami,
Juan Carlos Valenzuela-Tripodoro
Abstract:
The Roman domination in graphs is well-studied in graph theory. The topic is related to a defensive strategy problem in which the Roman legions are settled in some secure cities of the Roman Empire. The deployment of the legions around the Empire is designed in such a way that a sudden attack to any undefended city could be quelled by a legion from a strong neighbour. There is an additional condit…
▽ More
The Roman domination in graphs is well-studied in graph theory. The topic is related to a defensive strategy problem in which the Roman legions are settled in some secure cities of the Roman Empire. The deployment of the legions around the Empire is designed in such a way that a sudden attack to any undefended city could be quelled by a legion from a strong neighbour. There is an additional condition: no legion can move if doing so leaves its base city defenceless. In this manuscript we start the study of a variant of Roman domination in graphs: the triple Roman domination. We consider that any city of the Roman Empire must be able to be defended by at least three legions. These legions should be either in the attacked city or in one of its neighbours. We determine various bounds on the triple Roman domination number for general graphs, and we give exact values for some graph families. Moreover, complexity results are also obtained.
△ Less
Submitted 10 February, 2024;
originally announced February 2024.
-
Restrained condition on double Roman dominating functions
Authors:
Babak Samadi,
Nasrin Soltankhah,
H. Abdollahzadeh Ahangar,
M. Chellali,
Doost Ali Mojdeh,
S. M. Sheikholeslami,
J. C. Valenzuela-Tripodoro
Abstract:
We continue the study of restrained double Roman domination in graphs. For a graph $G=\big{(}V(G),E(G)\big{)}$, a double Roman dominating function $f$ is called a restrained double Roman dominating function (RDRD function) if the subgraph induced by $\{v\in V(G)\mid f(v)=0\}$ has no isolated vertices. The restrained double Roman domination number (RDRD number) $γ_{rdR}(G)$ is the minimum weight…
▽ More
We continue the study of restrained double Roman domination in graphs. For a graph $G=\big{(}V(G),E(G)\big{)}$, a double Roman dominating function $f$ is called a restrained double Roman dominating function (RDRD function) if the subgraph induced by $\{v\in V(G)\mid f(v)=0\}$ has no isolated vertices. The restrained double Roman domination number (RDRD number) $γ_{rdR}(G)$ is the minimum weight $\sum_{v\in 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 $γ$ and restrained Roman domination number $γ_{rR}$ are investigated in this paper by bounding $γ_{rdR}$ from below and above involving $γ_{r}$, $γ$ and $γ_{rR}$ for general graphs, respectively. We prove that $γ_{rdR}(T)\geq n+2$ for any tree $T\neq K_{1,n-1}$ of order $n\geq2$ and characterize the family of all trees attaining the lower bound. The characterization of graphs with small RDRD numbers is given in this paper.
△ Less
Submitted 3 February, 2022; v1 submitted 11 September, 2021;
originally announced September 2021.
