Title:
|
On signed edge domination numbers of trees (English) |
Author:
|
Zelinka, Bohdan |
Language:
|
English |
Journal:
|
Mathematica Bohemica |
ISSN:
|
0862-7959 (print) |
ISSN:
|
2464-7136 (online) |
Volume:
|
127 |
Issue:
|
1 |
Year:
|
2002 |
Pages:
|
49-55 |
Summary lang:
|
English |
. |
Category:
|
math |
. |
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 $\lbrace -1,1\rbrace $. If $\sum _{x\in N[e]} f(x)\ge 1$ for each $e\in E(G)$, then $f$ is called a signed edge dominating function on $G$. The minimum of the values $\sum _{x\in E(G)} f(x)$, taken over all signed edge dominating function $f$ on $G$, is called the signed edge domination number of $G$ and is denoted by $\gamma ^{\prime }_s(G)$. If instead of the closed neighbourhood $N_G[e]$ we use the open neighbourhood $N_G(e)=N_G[e]-\lbrace e\rbrace $, we obtain the definition of the signed edge total domination number $\gamma ^{\prime }_{st}(G)$ of $G$. In this paper these concepts are studied for trees. The number $\gamma ^{\prime }_s(T)$ is determined for $T$ being a star of a path or a caterpillar. Moreover, also $\gamma ^{\prime }_s(C_n)$ for a circuit of length $n$ is determined. For a tree satisfying a certain condition the inequality $\gamma ^{\prime }_s(T) \ge \gamma ^{\prime }(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 ^{\prime }_{st}(T)$. (English) |
Keyword:
|
tree |
Keyword:
|
signed edge domination number |
Keyword:
|
signed edge total domination number |
MSC:
|
05C05 |
MSC:
|
05C69 |
idZBL:
|
Zbl 0995.05112 |
idMR:
|
MR1895246 |
DOI:
|
10.21136/MB.2002.133984 |
. |
Date available:
|
2009-09-24T21:57:51Z |
Last updated:
|
2020-07-29 |
Stable URL:
|
http://hdl.handle.net/10338.dmlcz/133984 |
. |
Reference:
|
[1] E. Xu: On signed domination numbers of graphs.Discr. Math. (submitted). |
Reference:
|
[2] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs.Marcel Dekker, New York, 1998. MR 1605684 |
. |