%\def\paperauthorB{Author_B_fullname}
% you can add more authors using alphabets after \paperauthor
%------------------------------------------------------------------------------------------
% Do not delete this part starting from here and up to .....
%\setcounter{page}{1}
%\input{../../expages.tex}\setpagenumber{1}
%\input{expages.tex}\setpagenumber{1}
% Delete if you cannot get PS fonts working on your system.
% pdf-tex settings: detect automatically if run by latex or pdflatex
% compiling with pdflatex
% compiling with latex
% hyperrefs are active in the pdf file after conversion
%------------------------------------------------------------------------------------------
% This command replaces \name{The DAFx Crew} 
%\usepackage{layout}
%----------------------------------------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%% to here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[oneside]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{icma2021,amssymb,amsmath,mathrsfs}
\usepackage[pdftex,pdftitle={\papertitle}
\usepackage{hyperref}
\usepackage[pdftex]{graphicx}
\usepackage[figure,table]{hypcap}
\usepackage[dvips]{graphicx}
\usepackage[dvips,
colorlinks=false,           bookmarksnumbered, pdfstartview= XYZ	]{hyperref}
\usepackage[figure,table]{hypcap}

\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{LastRevised=Friday, November 12, 2021 22:15:17}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}

\def\papertitle{Graphs whose weak Roman domination number increases by the deletion of any edge}
\def\paperauthorA{Rihab Hamid, Nour Elhouda Bendahib, Mustapha Chellali and Nac\'{e}ra Meddah}
\ninept
\newif\ifpdf
\ifx\pdfoutput\relax
\else
\ifcase\pdfoutput
\pdffalse
\else
\pdftrue
\fi
\ifpdf 
\pdfcompresslevel=9
\else 
\fi
\newcommand\dsum{\displaystyle\sum}
\newcommand\dprod{\displaystyle\prod}
\affiliation{\paperauthorA}
{}

\input{tcilatex}

\begin{document}

\title{}
\author{}
\maketitle

\begin{abstract}
Let $f:V\rightarrow\{0,1,2\}$ be a function on a graph $G=(V,E)$. A vertex $v
$ with $f(v)=0$ is said to be undefended with respect to $f$ if it is not
adjacent to a vertex $u$ with $f(u)>0$. A function $f$ is called a weak
Roman dominating function (WRDF) if each vertex $v$ with $f(v)=0$ is
adjacent to a vertex $u$ with $f(u)>0$, such that the function $f^{\prime}$
defined by $f^{\prime}(v)=1$, $f^{\prime}(u)=f(u)-1$, and $f^{\prime}(w)=f(w)
$ for all $w\in V\setminus\{v,u\}$, has no undefended vertex. The weight of
a WRDF is the sum of its function values over all vertices, and the weak
Roman domination number $\gamma_{r}(G)$ is the minimum weight of a WRDF in $G
$. In this paper, we consider the effects of edge deletion on the weak Roman
domination number of a graph. We show that the deletion of an edge of $G$
can increase the weak Roman domination number by at most 1. Then we give a
necessary condition for $\gamma_{r}$-ER-critical graphs, that is, graphs $G$
whose weak Roman domination number increases by the deletion of any edge.
Restricted to the class of trees, we provide a constructive characterization
of all $\gamma_{r}$-ER-critical trees.\newline
{\small \textbf{Keywords: }Weak  Roman domination, weak Roman domination
critical graphs, trees.}
\end{abstract}

%\layout

% more pdf-tex settings:
\ifpdf % used graphic file format for pdflatex
\DeclareGraphicsExtensions{.png,.jpg,.pdf}  \else  
% used graphic file format for latex
\DeclareGraphicsExtensions{.eps}  \fi

\section{Introduction}

Let $G$ be a simple graph with vertex set $V=V(G)$ and edge set $E=E(G)$.
The \textit{open neighborhood} of a vertex $v\in V(G)$ is $N(v)=\{u\in V(G)\
|\ uv\in E(G)\}$, and its \textit{closed neighborhood} $N[v]=N(v)\cup \{v\}$%
. The \emph{degree} of a vertex $v$ is $\deg_{G}(v)=\left\vert
N(v)\right\vert $. A vertex of degree one is called a \textit{leaf}, and its
neighbor is called a \textit{stem}. A stem is said to be \textit{strong }if
it is adjacent to at least two leaves. Let $S(G)$ denote the set of stems of 
$G.$ An edge incident to a leaf is called a \textit{pendant edge}. A \textit{%
tree }is an acyclic connected graph. A tree $T$ is a \emph{double star} if
it contains exactly two vertices that are not leaves. A \textit{subdivided
star }$SS_{t}$ is a tree obtained from a star $K_{1,t}$ by replacing each
edge $uv$ of $K_{1,t}$ by a vertex $w$ and edges $uw$ and $vw$, while a 
\textit{double} \textit{subdivided star }$SS_{t}^{\ast}$ is obtained from $%
K_{1,t}$ by replacing each edge $uv$ of $K_{1,t}$ by two vertices $x,y$ and
edges $ux,xy$ and $yv.$ For a vertex $v$ in a rooted tree $T$, we denote by $%
C(v)$ and $D(v)$ the set of children and descendants, respectively, of $v$.
The \emph{maximal subtree} at $v$ is the subtree of $T$ induced by $D(v)\cup
\{v\}$, and is denoted by $T_{v}$.

Introduced in 2004 by Cockayne, Dreyer, Hedetniemi and Hedetniemi \cite{cdhh}%
, the concept of Roman domination is now well-studied with over 200 papers
published on it and its variations. For more on Roman domination, we refer
the reader to the book chapters and survey in \cite{cjsv,cjsv1,cjsv2}.

In this paper, we are interested in weak Roman domination, a {less 
restrictive} version of Roman domination, introduced by {Henning and 
Hedetniemi \cite{hh}. For a graph $G$, let $f:V(G)\rightarrow\{0,1,2\}$ be a
function. If $V_{i}=\{v\in V|f(v)=i\}$ for $i\in\{0,1,2\},$ then }$f$ can be
denoted by $f=${$(V_{0},V_{1},V_{2}).$ }A vertex $v$ with $f(v)=0$ is said
to be \textit{undefended} with respect to $f$ if it is not adjacent to a
vertex $u$ with $f(u)>0$. A function $f$ is called a \textit{weak Roman
dominating function} (WRDF) if each vertex $v$ with $f(v)=0$ is adjacent to
a vertex $u$ with $f(u)>0$, such that the function $f^{\prime}=(V_{0}^{%
\prime},V_{1}^{\prime},V_{2}^{\prime})$ defined by $f^{\prime}(v)=1$, $%
f^{\prime }(u)=f(u)-1$, and $f^{\prime}(w)=f(w)$ for all $w\in
V\setminus\{v,u\}$, has no undefended vertex. In this case, we will say that
vertex $u$ is a \textit{moving neighbor} for $v.$ Note that every vertex in $%
V_{0}$ has at least one moving neighbor in $V_{1}\cup V_{2}$. The \textit{%
weight} of a WRDF is the value $f(V)=\sum_{u\in V(G)}f(u),$ and the \textit{%
weak Roman domination number} $\gamma_{r}(G)$ is the minimum weight of a
WRDF in $G$. A WRDF $f$ is called a $\gamma_{r}(G)$-function if $%
f(V)=\gamma_{r}(G).$

In this paper, we study the effects of edge removal on the weak Roman
domination number of a graph. In particular, we consider graphs that are
\textquotedblleft critical\textquotedblright\ in the sense that the weak
Roman domination number increases\textbf{\ }upon the removal of an arbitrary
edge. Before presenting our main results, let us provide some useful
definitions and remark.

\begin{definition}
	\label{pf} If $f=${$(V_{0},V_{1},V_{2})$ is a }$\gamma_{r}(G)$-function, then
	for every vertex $v\in V_{1}\cup V_{2},$ let $P_{f}(v)$ be the set of all
	vertices in $N(v)\cap V_{0}$ for which $v$ is a moving neighbor.
\end{definition}

\begin{definition}
	\label{good}A vertex $x\in V(G)$ is said to be \textit{good}, if there exists
	a $\gamma_{r}(G)$-function $f$ such that $f(x)>0.$ Moreover,\textit{ a good}
	vertex $x\in V(G)$ is $1$\textit{-good,} if no $\gamma_{r}(G)$-function
	assigns a $2$ to $x.$
\end{definition}

\begin{remark}
	\label{support-f}For every graph $G$ with $S(G)\neq\emptyset$, there exists a
	$\gamma_{r}(G)$-function $f=(V_{0},V_{1},V_{2})$ such that $S(G)\subseteq
	V_{1}\cup V_{2}$.
\end{remark} 

\section{Edge removal}

We begin this section by showing that the removal of an edge in $G$ cannot
decrease the weak Roman domination number but can increase it by at most one.

\begin{proposition}
	\label{sameorincrease}For a graph $G$ and edge $uv\in E(G)$, $\gamma
	_{r}(G)\leq\gamma_{r}(G-uv)\leq\gamma_{r}(G)+1$.
\end{proposition}
To see the sharpness of the bounds in Proposition \ref{sameorincrease}, we
simply consider the example of a path $P_{4}=abcd,$ where $%
\gamma_{r}(P_{4}-bc)=\gamma_{r}(P_{4})=2$ while $\gamma_{r}(P_{4}-ab)=%
\gamma_{r}(P_{4})+1=3.$

According to Proposition \ref{sameorincrease}, an edge $e\in E(G)$ is said
to be \textit{critical }if $\gamma_{r}(G-uv)=\gamma_{r}(G)+1$. Moreover, a
graph $G$ is called $\gamma_{r}$\textit{-ER-critical} if $%
\gamma_{r}(G-e)=\gamma _{r}(G)+1$ for all $e\in E(G)$, that is, every edge
of $G$ is critical.

Our next result gives a necessary condition for $\gamma_{r}$-$ER$-critical
graphs.

\begin{proposition}
	\label{prop-gr}Let $G$ be $\gamma_{r}$-$ER$-critical graph. Then for every
	$\gamma_{r}(G)$-function $f=(V_{0},V_{1},V_{2})$ we have:
	
	\begin{itemize}
		\item[(1)] $V_{1}\cup V_{2}$ is an independent set.
		
		\item[(2)] If $v\in V_{2},$ then for every $x\in P_{f}(v),$ $N(x)\cap
		V_{0}=\emptyset.$ In particular $P_{f}(v)$ is independent.
		
		\item[(3)] For every $u,v\in V_{1}\cup V_{2},$ no edge joins $P_{f}(v)$ and
		$P_{f}(u)$.
		
		\item[(4)] For every vertex $v\in V_{0},$ $\left\vert N(v)\cap(V_{1}\cup
		V_{2})\right\vert \leq2.$ In particular, $\left\vert N(v)\cap V_{1}\right\vert
		\leq2,$ $\left\vert N(v)\cap V_{2}\right\vert \leq1$ and if $N(v)\cap
		V_{2}\neq\emptyset,$ then $N(v)\cap V_{1}=\emptyset.$
		
		\item[(5)] If $G$ is connected, then $\left\vert V_{2}\right\vert \leq1.$
	\end{itemize}
\end{proposition}

\unitlength=0.64cm 
\begin{figure}[h]
%%%%%%%%%%%%%%%%%%%%%%%fig1%%%%%%%%%%%%%%%%%%%%%%
\par
\begin {picture}(10,7)(-11,-0.5)
	\put(0,0){\circle{0.25}}
	\put(0,1){\circle*{0.25}}
	\put(0,2){\circle{0.25}}
	\put(0,4){\circle{0.25}}
	\put(0,5){\circle*{0.25}}
	\put(0,6){\circle{0.25}}
	\put(1,3){\circle*{0.25}}
	\put(2,0){\circle{0.25}}
	\put(2,1){\circle*{0.25}}
	\put(2,2){\circle{0.25}}
	\put(2,4){\circle{0.25}}
	\put(2,5){\circle*{0.25}}
	\put(2,6){\circle{0.25}}
	\put(0,0.15){\line(0,1){1.7}}
	\put(0,4.15){\line(0,1){1.7}}
	\put(2,0.15){\line(0,1){1.7}}
	\put(2,4.15){\line(0,1){1.7}}
	\put(0.13,2.15){\line(1,1){1.75}}
	\put(0.13,3.87){\line(1,-1){1.75}}
	\put(0.15,2){\line(1,0){1.7}}
	\put(-0.5,2){\small{$u$}}
	\put(2.2,2){\small{$v$}}
\end{picture}
\caption{Graph $G$}
\label{cactus}
\end{figure}

We note that the converse of Proposition \ref{prop-gr} is not true. To see
consider the graph $G$ shown in Figure 1, where $G$ has a unique $\gamma
_{r}(G)$-function $f$ that assigns a $1$ to dark vertices of $G$ and a $0$
to the remaining vertices. Clearly $f$ satisfies all conditions of
Proposition \ref{prop-gr}, but $\gamma_{r}\left( G-uv\right) =$ $%
\gamma_{r}(G)=5.$

The following corollary is an immediate consequence of Remark \ref{support-f}
and Proposition \ref{prop-gr}.

\begin{corollary}
	\label{sup-st}If a graph $G$ is a $\gamma_{r}$-$ER$-critical, then the set of
	stems is independent.
\end{corollary}

\begin{proposition}
	\label{ere}If $G$ is a connected $\gamma_{r}$-$ER$-critical graph, then there
	is a $\gamma_{r}(G)$-function $f=(V_{0},V_{1},V_{2})$ such that $\lvert
	V_{2}\lvert=1$ if and only if $G$ is a star of order at least $4$.
\end{proposition}

\section{$\protect\gamma_{r}$-$ER$-critical trees}

In the aim to characterize $\gamma_{r}$\textit{-}$ER$\textit{-}critical
trees, let $\mathcal{H}$ be the collection of all trees that can be obtained
from a sequence $T_{1},T_{2},...,T_{p},$ $(p\geq1),$ of trees $T$ such that $%
T_{1}$ is the path $P_{2}$, and if $p\geq2,$ then $T_{i+1}$ can be obtained
recursively from $T_{i}$ by one of the two operations $\mathcal{O}_{1}$ and $%
\mathcal{O}_{2}$ defined below. Let one the vertices of $T_{1}$ be
considered a stem and the other a leaf. Let also $H_{t}$ be the tree
obtained from a double subdivided star\textit{\ }$SS_{t}^{\ast},$ with $%
t\geq2$, centered at $y$ by adding a new vertex $z$ and the edge $yz$ (for
example, see the tree $H_{3}$ shown in Figure 2). It is worth noting that $%
d_{H_{t}}(y)=t+1$ and $\gamma_{r}(H)=t+2$. Recall that a \emph{pendant path} 
$P$ of a graph $G$ is an induced path such that one of the endvertices is a
leaf in $G$, and its other endvertex is the only vertex of $P$ adjacent to
some vertex in $G-P$.

\unitlength=0.64cm 
\begin{figure}[h]
%%%%%%%%%%%%%%%%%%%%%%%fig1%%%%%%%%%%%%%%%%%%%%%%
\par
\begin {picture}(10,5.5)(-11,-0.5)
	\put(0,0){\circle*{0.25}}
	\put(0,1){\circle*{0.25}}
	\put(0,2){\circle*{0.25}}
	\put(1,0){\circle*{0.25}}
	\put(1,1){\circle*{0.25}}
	\put(1,2){\circle*{0.25}}
	\put(1,3){\circle*{0.25}}
	\put(1,4){\circle*{0.25}}
	\put(2,0){\circle*{0.25}}
	\put(2,1){\circle*{0.25}}
	\put(2,2){\circle*{0.25}}
	\put(0,0){\line(0,1){2}}
	\put(1,0){\line(0,1){4}}
	\put(2,0){\line(0,1){2}}
	\put(0,2){\line(1,1){1}}
	\put(1,3){\line(1,-1){1}}
	\put(1.2,3){\small{$y$}}
	\put(1.2,4){\small{$z$}}
\end{picture}
\caption{Tree $H_{3}$}
\end{figure}

\begin{itemize}
\item \textbf{Operation }$\mathcal{O}$\textbf{$_{1}$: }Assume $x$ is a stem
of $T_{i}$. Then $T_{i+1}$ is obtained from $T_{i}$ by adding a path $%
P_{5}=x_{1}x_{2}x_{3}x_{4}x_{5}$ attached by an edge $x_{5}x$.

\item \textbf{Operation }$\mathcal{O}_{2}:$ Assume $u$ is \ vertex of $T_{i}$
which is either a stem or belongs to a pendant path of length $3$. Then $%
T_{i+1}$ is obtained from $T_{i}$ by adding a copy of $H_{t}$ attached by an
edge $uz$.
\end{itemize}

Our main result is the following. 

\begin{theorem}
\label{main_trees}A non-trivial tree $T$ is $\gamma_{r}$-$ER$-critical if and
only if $T$ is a star of order at least four or $T\in\mathcal{H}$.
\end{theorem}

\section{conclusions}

In this paper, we showed that the delection of an edge of a graph $G$ can
increase the weak Roman domination number by at most 1. Then we established
a necessary condition for graphs whose number of Weak Roman domination
number increases by the removal of any edge. Finally, we provided a
constructive characterization of all $\gamma _{r}$-ER-critical trees. We
close by mentioning that it is also worthwhile to characterize other $\gamma
_{r}$-ER-critical graphs such as cactus graphs. 

\begin{thebibliography}{9}
\bibitem{cjsv} M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. 
Volkmann, Roman domination in graphs, in: \emph{Topics in Domination in
Graphs}, (Eds), T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Springer
Nature  Switzerland AG 2020.

\bibitem{cjsv1} M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. 
Volkmann, Varieties of Roman domination, in: \emph{Structures of Domination
in Graphs}, Eds. T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Springer 
International Publishing 2021.

\bibitem{cjsv2} M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. 
Volkmann, Varieties of Roman domination II, \emph{AKCE J. Graphs Combin.}
17:3  (2020) 966--984.

\bibitem{cdhh} E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. 
Hedetniemi, Roman domination in graphs, \emph{Discrete Math.} 278 (2004)
11--22.

\bibitem{hh} M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire -
A  new strategy, \emph{Discrete Math. }266 (2003) 239--251.
\end{thebibliography}

\end{document}
