On The Signed Edge Domination Number of Graphs

Abstract

Let ${\gamma }_s^{\prime }(G)$ be the signed edge domination number of G. In 2006, Xu conjectured that: for any $2$-connected graph G of order $n(n\ge 2),$ ${\gamma }_s^{\prime }(G)\ge 1$. In this article we show that this conjecture is not true. More precisely, we show that for any positive integer $m$, there exists an $m$-connected graph $G$ such that ${\gamma }_s^{\prime }(G)\le -\frac{m}{6}|V(G)|.$ Also for every two natural numbers $m$ and $n$, we determine ${\gamma }_s^{\prime }(K_{m,n})$, where $K_{m,n}$ is the complete bipartite graph with part sizes $m$ and $n$.