# Article

Full entry | PDF   (0.2 MB)
Keywords:
signed edge domination; signed edge total dominating function; signed edge total domination number
Summary:
The open neighborhood $N_G(e)$ of an edge $e$ in a graph $G$ is the set consisting of all edges having a common end-vertex with $e$. Let $f$ be a function on $E(G)$, the edge set of $G$, into the set $\{-1, 1\}$. If $\sum _{x\in N_G(e)}f(x) \geq 1$ for each $e\in E(G)$, then $f$ is called a signed edge total dominating function of $G$. The minimum of the values $\sum _{e\in E(G)} f(e)$, taken over all signed edge total dominating function $f$ of $G$, is called the signed edge total domination number of $G$ and is denoted by $\gamma _{st}'(G)$. Obviously, $\gamma _{st}'(G)$ is defined only for graphs $G$ which have no connected components isomorphic to $K_2$. In this paper we present some lower bounds for $\gamma _{st}'(G)$. In particular, we prove that $\gamma _{st}'(T)\geq 2-m/3$ for every tree $T$ of size $m\geq 2$. We also classify all trees $T$ with $\gamma _{st}'(T)=2-m/3$.
References:
[1] Karami, H., Khodkar, A., Sheikholeslami, S. M.: Signed edge domination numbers in trees. Ars Combinatoria (to appear). MR 2568858
[2] West, D. B.: Introduction to Graph Theory. Prentice-Hall, Inc (2000). MR 1367739
[3] Xu, B.: On signed edge domination numbers of graphs. Discrete Mathematics 239 (2001), 179-189. DOI 10.1016/S0012-365X(01)00044-9 | MR 1850997 | Zbl 0979.05081
[4] Xu, B.: On lower bounds of signed edge domination numbers in graphs. J. East China Jiaotong Univ. 1 (2004), 110-114 Chinese.
[5] Zelinka, B.: On signed edge domination numbers of trees. Math. Bohem. 127 (2002), 49-55. MR 1895246 | Zbl 0995.05112

Partner of