Edge Roman domination on graphs

Abstract

An edge Roman dominating function of a graph $G$ is a function $f:E(G)\to \{0,1,2\}$ satisfying the condition that every edge $e$ with $f(e)=0$ is adjacent to some edge $e^{\prime }$ with $f(e^{\prime })=2$. The edge Roman domination number of $G$, denoted by ${\gamma }_R^{\prime }(G)$, is the minimum weight $w(f)={\sum }_{e\in E(G)}f(e)$ of an edge Roman dominating function $f$ of $G$. This paper disproves a conjecture of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad stating that if $G$ is a graph of maximum degree $\Delta$ on $n$ vertices, then ${\gamma }_R^{\prime }(G)\le \lceil \frac{\Delta }{\Delta +1}n\rceil$. While the counterexamples having the edge Roman domination numbers $\frac{2\Delta -2}{2\Delta -1}n$, we prove that $\frac{2\Delta -2}{2\Delta -1}n+\frac{2}{2\Delta -1}$ is an upper bound for connected graphs. Furthermore, we provide an upper bound for the edge Roman domination number of $k$-degenerate graphs, which generalizes results of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad. We also prove a sharp upper bound for subcubic graphs. In addition, we prove that the edge Roman domination numbers of planar graphs on $n$ vertices is at most $\frac{6}{7}n$, which confirms a conjecture of Akbari and Qajar. We also show an upper bound for graphs of girth at least five that is 2-cell embeddable in surfaces of small genus. Finally, we prove an upper bound for graphs that do not contain $K_{2,3}$ as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.