Lower bounds on signed edge total domination numbers in graphs

Karami, H. ; Sheikholeslami, S. M. ; Khodkar, Abdollah

Czechoslovak Mathematical Journal, Tome 58 (2008) no. 3, pp. 595-603

Abstract (VO)

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$.

Détail

Classification : 05C05, 05C69
Keywords: signed edge domination; signed edge total dominating function; signed edge total domination number