On signed edge domination numbers of trees. (English) Zbl 0995.05112

Summary: The signed edge domination number of a graph is an edge variant of the signed domination number. The closed neighbourhood \(N_G[e]\) of an edge \(e\) in a graph \(G\) is the set consisting of \(e\) and of all edges having a common end vertex with \(e\). Let \(f\) be a mapping of the edge set \(E(G)\) of \(G\) into the set \(\{-1,1\}\). If \(\sum_{x\in N[e]} f(x)\geq 1\) for each \(e\in E(G)\), then \(f\) is called a signed edge dominating functions on \(G\). The minimum of the values \(\sum _{x\in E(G)} f(x)\), taken over all signed edge dominating functions \(f\) on \(G\), is called the signed edge domination number of \(G\) and is denoted by \(\gamma_s'(G)\). If instead of the closed neighbourhood \(N_G[e]\) we use the open neighbourhood \(N_G(e)=N_G[e]-\{e\}\), we obtain the definition of the signed edge total domination number \(\gamma_{st}'(G)\) of \(G\). In this paper these concepts are studied for trees. The number \(\gamma_s'(T)\) is determined for \(T\) being a star of a path or a caterpillar. Also \(\gamma_s'(C_n)\) for a circuit of length \(n\) is determined. For a tree satisfying a certain condition the inequality \(\gamma_s'(T) \geq \gamma'(T)\) is stated. An existence theorem for a tree \(T\) with a given number of edges and given signed edge domination number is proved. At the end similar results are obtained for \(\gamma_{st}'(T)\).


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C05 Trees
Full Text: DOI EuDML