% 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} 
%\affiliation{\paperauthorB}
%{\small{LAMDA-RO Laboratory, Department of Mathematics  %University of Blida}}
%\usepackage{layout}
%------------------------------------------------------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%% to here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[oneside]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{icma2021,amssymb,amsmath,mathrsfs}
\usepackage{mathptmx}
\usepackage[pdftex,
pdftitle={\papertitle}
\usepackage{\paperauthorA,\paperauthorB}
\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=Sunday, November 07, 2021 19:45:25}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}

\def\papertitle{The Effect of Edge lifting on Roman domination in graphs}
\def\paperauthorA{Meraimi Hicham}
\def\paperauthorB{Mustapha Chellali}
\ninept
\newif\ifpdf
\ifx\pdfoutput\relax
\else
\ifcase\pdfoutput
\pdffalse
\else
\pdftrue
\fi
\ifpdf 
\pdfcompresslevel=9
\else 
\fi
\newtheorem{coro}[theorem]{Corollary}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{lemme}[theorem]{Lemma}
\newcommand\dsum{\displaystyle\sum}
\newcommand\dprod{\displaystyle\prod}
\affiliation{\paperauthorA, \paperauthorB}
{{\small{Faculty of Mathematics, Laboratory L'IFORCE,(USTHB) Algiers, Algeria.}}\\{\small{LAMDA-RO Laboratory, Department of Mathematics University of Blida}}}

\input{tcilatex}

\begin{document}

\title{The Effect of Edge lifting on Roman domination in graphs}
\author{}
\maketitle

\begin{abstract}
Let $G$ be a graph, and let $uxv$ be an induced path centered at $x$. An
edge lift defined on $uxv$ is the action of removing edges $ux$ and $vx$
while adding the edge $uv$ to the edge set of $G$. In this paper, we
initiate the study of the effects of edge lifting on the Roman domination
number of a graph, where various properties are established. A
characterization of all trees for which every edge lift increases the Roman
domination number is provided. Moreover, we characterize the edge lift of a
graph decreasing the Roman domination number, and we show that there are no
graphs with at most one cycle for which every possible edge lift can have
this property.
\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}

We consider simple graphs $G$ with vertex set $V=V(G)$ and edge set $E=E(G)$%
. The \textit{open neighborhood} of a vertex $v\in V$ is the set $%
N_{G}(v)=N(v)=\{u\in V\ |\ uv\in E\}$, the \emph{closed neighborhood }of $v$
is the set $N_{G}[v]=N[v]=N_{G}(v)\cup\{v\}$, and the \emph{degree} of $v$
is $\deg_{G}(v)=|N(v)|$.A vertex of degree one is called a\textit{leaf} and
its neighbor a \textit{support vertex.} If $v$ is a support vertex, then $%
L_{v}$ will denote the set of the leaves attached at $v$. An \emph{$S$%
-external private neighbor} of a vertex $v\in S$ is a vertex $u\in
V\setminus S$ which is adjacent to $v$ but to no other vertex of $S$. The
set of all $S$-external private neighbors of $v\in S$ is called the \emph{$S$%
-external private neighbor set} of $v$ and is denoted $\mathrm{epn}(v,S)$.
Let $uxv$ be an induced path in a graph $G$. We say that $ux$ and $vx$ are 
\textit{lifted} \textit{off} $x$ and call the operation of removing $ux$ and 
$vx$ and adding $uv$ to $E(G)$ an \textit{edge lift}. Moreover, the graph
formed from $G$ by an edge lift on $uxv$ is denoted as $G_{x}^{uv}$, where $%
V(G_{x}^{uv})=V(G)$ and $E(G_{x}^{uv})=\{uv\}\cup E(G)\setminus\{ux,vx\}$.
The process of \emph{edge lifting} (also called \emph{edge splitting}) was
introduced by Lov\'{a}sz in \cite{l1,l2} to study edge connectivity in
graphs, and has been extended in 2011 to domination in graphs (see \cite%
{des1,des2}) and in 2013 to total domination in graphs (see \cite{des3}) to
study its effects on the corresponding domination parameters. Our aim is to
study the effect of edge lifting with respect to Roman domination. A
function \textit{\ }$f:V\rightarrow\{0,1,2\}$ is a \textit{Roman dominating
function}, abbreviated RDF,\textit{\ }on a graph $G$ if for every vertex $%
v\in V$ with $f(v)=0$, there exists a neighbor $u\in N(v)$ with $f(u)=2$.
The \textit{weight} of an RDF $f$ is the sum $f(V)=\sum_{v\in V}f(v)$. The
minimum weight of an RDF on $G$ is called the \textit{Roman domination number%
} of $G$ and is denoted by $\gamma_{R}(G)$. {An RDF on $G$ with weight $%
\gamma_{R}(G)$ is called a }$\gamma_{R}(G)$\textit{-function. }{Notice that
an RDF $f$ on {$G$} can be {denoted by }$(V_{0},V_{1},V_{2})$ (or $%
(V_{0}^{f},V_{1}^{f},V_{2}^{f})$ to refer to }$f$), {where $V_{j}=\{v\in
V\mid f(v)=j\}$ for $j\in\{0,1,2\}$. }The Roman domination number was
introduced by Cockayne et al.~\cite{Roman} in 2004 and was inspired by the
work of ReVelle and Rosing~\cite{ReVelle} and Stewart~\cite{Stewart}. For
more information on Roman domination, we refer the reader to the book
chapter \cite{cjsv}. All graphs considered are connected and contain at
least one induced path on three vertices. For every graph $G$ we define the
following weak partition (in which a subset may be empty) $%
A(G)=(A^{+}(G),A^{-}(G),A^{0}(G)),$ where 
\begin{align*}
A^+(G) & =\{uxv\in A(G)|\gamma_R(G_x^uv)>\gamma_R(G)\} \\
A^-(G) & =\{uxv\in A(G)|\gamma_R(G_x^uv)<\gamma_R(G)\} \\
A^0(G) & =\{uxv\in A(G)|\gamma _R(G_x^uv)=\gamma_R(G)\}.
\end{align*}
Before going further, we need to show that an edge lift on any induced path $%
P_{3}$ in $A(G)$ can decrease the Roman domination number by at most one and
increase it by at most two.

\begin{theorem}
\label{Borne}For every graph $G$ and every path $uxv\in A(G),$\[
\gamma_R(G)-1\leq\gamma_R(G_x^uv)\leq\gamma_R(G)+2. \]
\end{theorem}
\begin{figure}[h]
\unitlength=0.7cm
\par
\center%
\begin{picture}(8,5)(0,2) \put(0.8,1.5){$a$} \put(1.3,1.5){$b$} \put(1.8,4.2){$c$}
\put(3.5,4.2){$d$} \put(3.5,6){$e$} \put(1,2){\circle*{0.2}} \put
(1.5,2){\circle*{0.2}} \put(2,2){\circle*{0.2}} \put(2.5,2){\circle*{0.2}}
\put(2,4){\circle*{0.2}} \put(4,4){\circle*{0.2}} \put(4,6){\circle*{0.2}}
\put(6,4){\circle*{0.2}} \put(5.5,2){\circle*{0.2}} \put(6,2){\circle*{0.2}}
\put(6.5,2){\circle*{0.2}} \put(7,2){\circle*{0.2}} \put(2,4){\line(1,0){4}}
\put(2,4){\line(-1,-2){1}} \put(2,4){\line(-1,-4){0.5}} \put(2,4){\line
(0,-1){2}} \put(2,4){\line(1,-4){0.5}} \put(6,4){\line(-1,-4){0.5}}
\put(6,4){\line(0,-1){2}} \put(6,4){\line(1,-4){0.5}} \put(6,4){\line
(1,-2){1}} \put(4,4){\line(0,1){2}}
\end{picture}
\caption{Graph $G$.{}}
\label{etiq G}
\end{figure}
It can be noted that the upper and lower bounds of Theorem 1 are sharp as
can be seen by the graph $G$ in Figure \ref{etiq G}, where $\gamma_{R}(G)=5$%
, $\gamma_{R}(G_{c}^{ab})=7$ and $\gamma_{R}(G_{d}^{ec})=4.$

\section{$\protect\gamma_{RL}^{+}-$critical graphs}

We begin by giving a necessary condition for $\gamma_{RL}^{+}$-critical
graphs. 
\begin{theorem}
\label{T1}If $G$ is a connected $\gamma_{RL}^{+}$-critical graph, then for
every $\gamma_{R}(G)$-function $f=(V_{0},V_{1},V_{2})$ we have:
\begin{itemize}
\item[1)] $V_{1}=\emptyset.$ \item[2)] $V_{2}$ is an independent set.
\item[3)] For all $x\in V_{2},$ $|\mathrm{epn}(x,V_{2})|\geq2$. \item[4)] For
all $x\in V_{0},$ $|N(x)\cap V_{2}|\leq2.$
\end{itemize}
\end{theorem}
We note that the converse of Theorem \ref{T1} is not true as can be seen by
the graph $H$ in Figure \ref{etiq H} which satisfies the four conditions of
Theorem \ref{T1} but $\gamma_{R}(H_{b}^{ac})=\gamma_{R}(H)=4$. 
\begin{figure}[h]
\unitlength=0.7cm
\par
\center%
\begin{picture}(8,3)(0,1) \put(3.9,3.2){$a$} \put(2.9,2.2){$b$} \put(3.9,0.6){$c$}
\put(2,1){\circle*{0.2}} \put(2,2){\circle*{0.2}} \put(2,3){\circle*{0.2}}
\put(3,2){\circle*{0.2}} \put(4,1){\circle*{0.2}} \put(4,3){\circle*{0.2}}
\put(5,2){\circle*{0.2}} \put(6,1){\circle*{0.2}} \put(6,2){\circle*{0.2}}
\put(6,3){\circle*{0.2}} \put(3,2){\line(-1,1){1}} \put(3,2){\line(-1,0){1}}
\put(3,2){\line(-1,-1){1}} \put(3,2){\line(1,1){1}} \put(3,2){\line(1,-1){1}}
\put(5,2){\line(-1,1){1}} \put(5,2){\line(-1,-1){1}} \put(5,2){\line(1,1){1}}
\put(5,2){\line(1,0){1}} \put(5,2){\line(1,-1){1}}
\end{picture}
\caption{Graph $H$.{}}
\label{etiq H}
\end{figure}
The next corollary is immediate from Theorem \ref{T1}-(1).

\begin{coro}
If $G$ is a connected $\gamma_{RL}^{+}$-critical graph, then $\gamma_{R}(G) $
is even.
\end{coro}

In \cite{Roman}, Cockayne et al. showed that for every graph $G,$ $\gamma
_{R}(G)\leq2\gamma(G),$ and called the graphs attaining equality \textit{%
Roman graphs}. Moreover, they gave a necessary and sufficient condition for
Roman graphs. 
\begin{proposition}
[\cite{Roman}]\label{RG}A graph $G$ is Roman if and only if it has a
$\gamma_{R}$-function $f=(V_{0},V_{1},V_{2})$ with $V_{1}=\emptyset$.
\end{proposition}
Our next result shows that $\gamma_{RL}^{+}(G)$-critical graphs $G$ are
Roman, that is $\gamma_{R}(G)=2\gamma(G).$ 
\begin{proposition}
\label{+RG}If $G$ is $\gamma_{RL}^{+}(G)$-critical, then $G$ is a Roman
graph.
\end{proposition}
Our next aim is to give a constructive characterization of $\gamma_{RL}^{+}$%
-critical trees. We first show that $\gamma_{RL}^{+}$-critical trees have
unique minimum Roman dominating functions. For this purpose we recall the
following result due to Gunther et al. \cite{mghr}. 
\begin{theorem}
[\cite{mghr}]\label{Dset}A tree $T$ of order at least three has a unique
minimum dominating set $D$ if and only if every vertex in $D$ has at least two
private neighbors other than itself.
\end{theorem}
\begin{proposition}
\label{fu}If $T$ is a $\gamma_{RL}^{+}$-critical tree, then $T$ has a unique
$\gamma_{R}(T)$-function.
\end{proposition}
We note that the converse of Proposition \ref{fu} is not true. To see,
consider the double star $T=S_{p,q}$, with $p\geq q\geq3$, where $T$ has a
unique $\gamma_{R}(T)$-function but $T$ is not $\gamma_{RL}^{+}$-critical.
\bigskip Let $\mathcal{F}$ be the family of trees $T=T_{k}$ that can be
obtained as follows. Let $T_{1}$ be a star $K_{1,t}$ ($t\geq2$) centered at $%
x$ and let $f_{1}=(L_{x},\emptyset,\{x\})$ be an RDF of $T_{1}$. If $k>1$,
then $T_{i+1}$ can be obtained recursively from $T_{i}$ by one of the
following two operations. For any tree $T_{i}$ of ${\mathcal{F}}$, we let $%
f_{i}=(V_{0}^{i},V_{1}^{i},V_{2}^{i})$.

\begin{itemize}
\item Operation $\mathcal{O}_{1}$: Add a star $K_{1,t}$ $(t\geq3)$ centered
at $s$ by joining a leaf $z$ of the star to a vertex $h$ of $V_{2}^{i}$ such
that $\mathrm{epn}(h,V_{2}^{i})=N_{T_{i}}(x)\cap V_{0}^{i}$. Let $%
f_{i+1}(y)=f_{i}(y)$ for every $y\in V(T_{i}),$ $f_{i+1}(s)=2$ and $%
f_{i+1}(u)=0$ for each neighbor $u$ of $s.$

\item Operation $\mathcal{O}_{2}$: Add a star $K_{1,t}$ $(t\geq2)$ centered
at $s$ by joining a leaf $z$ of the star to a leaf $d$ of $T_{i}$ . Let $%
f_{i+1}(y)=f_{i}(y)$ for every $y\in V(T_{i}),$ $f_{i+1}(s)=2$ and $%
f_{i+1}(u)=0$ for each neighbor $u$ of $s.$
\end{itemize}

Using both operation we could prove: 
\begin{theorem}
\label{maintree}A tree $T$ of order at least $3$ is $\gamma_{RL}^{+}$-critical
if and only if $T\in\mathcal{F}$.
\end{theorem}

\section{$\protect\gamma_{RL}^{-}$-critical graphs}

We begin by giving a necessary and sufficient condition for induced paths $%
P_{3}$ of a graph $G$ to be in $A^{-}(G)$. 
\begin{theorem}
\label{G-uvx}Let $G$ be a graph and let $uxv$ be an induced path $P_{3}$ in
$G$. Then $uxv\in A^{-}(G)$ if and only if there is a $\gamma_{R}(G)$-function
$g=(V_{0}^{g},V_{1}^{g},V_{2}^{g})$ such that:
\begin{itemize}
\item[1) ] One of $v$ and $u$ belongs to $V_{1}^{g}$, say $v$. \item[2) ]
$u\in V_{2}^{g}$. Moreover, if $N(u)\cap V_{2}^{g}\neq\emptyset$, then
$|\mathrm{epn}(u,V_{2}^{g})|\geq2$. \item[3) ] $x\in V_{0}^{g}$ and $|N(x)\cap
V_{2}^{g}|\geq2$.
\end{itemize}
\end{theorem}
As an immediate consequence to Theorem \ref{G-uvx} we obtain the following
corollary.

\begin{coro}
\label{degre}If $G$ is a $\gamma_{RL}^{-}$-critical graph, then for every
induced path $uxv$ in $G$, we have:

\begin{itemize}
\item[1) ] $\deg_{G}(x)\geq3.$

\item[2) ] $\max\{\deg_{G}(u),\deg_{G}(v)\}\geq2$.
\end{itemize}
\end{coro}

In the sequel, we shall show that no graph with at most one cycle is a $%
\gamma_{RL}^{-}$-critical. Let us start with the class of trees 
\begin{theorem}
\label{notrees}No tree on at least three vertices is $\gamma_{RL}^{-}%
$-critical.
\end{theorem}
Recall that the \textit{corona} of the graph $G,$ denoted by $G\circ K_{1},$
is the graph formed from $G$ by adding a new vertex $v^{\prime}$ and the
pendant edge $vv^{\prime}$ for each $v\in V(G).$ 
\begin{theorem}
\label{unicyle}No unicycle graph is $\gamma_{RL}^{-}$-critical.
\end{theorem}
According to Theorems \ref{notrees} and \ref{unicyle}, one wonders if there
are $\gamma_{RL}^{-}$-critical graphs. The answer is yes as it can be seen
by the graph $G^{\ast}$ illustrated in Figure \ref{etiq G star}.\textbf{\ }%
Furthermore, we conjecture that $G^{\ast}$ is the only cactus graph which is 
$\gamma_{RL}^{-}$-critical. 
\begin{figure}[h]
\unitlength=0.7cm
\par
\center%
\begin{picture}(6,5)(0,1) \put(2,2){\circle*{0.2}} \put(4,2){\circle*{0.2}} \put
(3,4){\circle*{0.2}} \put(1,2){\circle*{0.2}} \put(5,2){\circle*{0.2}}
\put(1.5,1){\circle*{0.2}} \put(4.5,1){\circle*{0.2}} \put(2.5,5){\circle
*{0.2}} \put(3.5,5){\circle*{0.2}} \put(1,2){\line(1,0){4}} \put
(1.5,1){\line(1,2){2}} \put(2.5,5){\line(1,-2){2}} \put(2.5,5){\line(1,0){1}}
\put(1,2){\line(1,-2){0.5}} \put(5,2){\line(-1,-2){0.5}}
\end{picture}
\caption{Graph $G^{\ast}$}
\label{etiq G star}
\end{figure}

\begin{thebibliography}{99}
\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, to appear 2020.

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

\bibitem{des1} W.J. Desormeaux, A.J. Hall, T.W. Haynes, D. Koessler, M.A.
Langston, S.A. Rickett, and H. Scott, Edge lifting and domination in graphs. 
\textit{Bull. Inst. Combin. Appl.}, 63 (2011) 77--86.

\bibitem{des2} W.J. Desormeaux, T.W. Haynes and M.A. Henning, Domination
edge lift critical trees. \textit{Quaest. Math.},\textit{\ }34 (2011) 1--12.

\bibitem{des3} W.J. Desormeaux, T.W. Haynes and M.A. Henning, Edge lifting
and total domination in graphs. \textit{J. Comb. Optim., }25 (2013) 47--59.

\bibitem{l1} L. Lov\'{a}sz, Lecture, Conference of Graph Theory, Prague,
1974.

\bibitem{l2} L. Lov\'{a}sz, \emph{Combinatorial Problems and Exercises}, 2nd
Ed., North-Holland, New York, 1993.

\bibitem{mghr} G. Gunther, B. Hartnell, L.R. Markus and D. Rall, Graphs with
unique minimum dominating sets. \textit{Congr.Numer}., 101 (1994) 55--63.

\bibitem{ReVelle} C.S. ReVelle and K.E. Rosing, Defendens imperium romanum:
a classical problem in military strategy. \textit{Amer. Math. Monthly} 107
(7) (2000) 585--594.

\bibitem{Stewart} I. Stewart, Defend the Roman Empire! \textit{Sci. Amer.,}
281 (6) (1999) 136--139.
\end{thebibliography}

\end{document}
