Upper bounds on the signed edge domination number of a graph

Abstract

A signed edge domination function (or SEDF) of a simple graph $G=(V,E)$ is a function $f:E\to \{1,-1\}$ such that ${\sum }_{e^{\prime }\in N[e]}f(e^{\prime })\ge 1$ holds for each edge $e\in E$, where $N[e]$ is the set of edges in $G$ that share at least one endpoint with $e$. Let ${\gamma }_s^{\prime }(G)$ denote the minimum value of $f(G)$ among all SEDFs $f$, where $f(G)={\sum }_{e\in E}f(e)$.In 2005, Xu conjectured that ${\gamma }_s^{\prime }(G)\le n-1$, where $n$ is the order of $G$. This conjecture has been proved for the two cases $v_{odd}(G)=0$ and $v_{even}(G)=0$, where $v_{odd}(G)$ (resp. $v_{even}(G)$) is the number of odd (resp. even) vertices in $G$. This article proves Xu's conjecture for $v_{even}(G)\in \{1,2\}$. We also show that for any simple graph $G$ of order $n$, ${\gamma }_s^{\prime }(G)\le n+v_{odd}(G)/2$ and ${\gamma }_s^{\prime }(G)\le n-2+v_{even}(G)$ when $v_{even}(G)>0$, and thus ${\gamma }_s^{\prime }(G)\le (4n-2)/3$. Our result improves the best current upper bound of ${\gamma }_s^{\prime }(G)\le \lceil 3n/2\rceil$.