# Signed domination and signed domatic numbers of digraphs

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 3, page 415-427
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topLutz Volkmann. "Signed domination and signed domatic numbers of digraphs." Discussiones Mathematicae Graph Theory 31.3 (2011): 415-427. <http://eudml.org/doc/270815>.

@article{LutzVolkmann2011,

abstract = {Let D be a finite and simple digraph with the vertex set V(D), and let f:V(D) → -1,1 be a two-valued function. If $∑_\{x ∈ N¯[v]\}f(x) ≥ 1$ for each v ∈ V(D), where N¯[v] consists of v and all vertices of D from which arcs go into v, then f is a signed dominating function on D. The sum f(V(D)) is called the weight w(f) of f. The minimum of weights w(f), taken over all signed dominating functions f on D, is the signed domination number $γ_S(D)$ of D. A set $\{f₁,f₂,...,f_d\}$ of signed dominating functions on D with the property that $∑_\{i = 1\}^d f_i(x) ≤ 1$ for each x ∈ V(D), is called a signed dominating family (of functions) on D. The maximum number of functions in a signed dominating family on D is the signed domatic number of D, denoted by $d_S(D)$. In this work we show that $4-n ≤ γ_S(D) ≤ n$ for each digraph D of order n ≥ 2, and we characterize the digraphs attending the lower bound as well as the upper bound. Furthermore, we prove that $γ_S(D) + d_S(D) ≤ n + 1$ for any digraph D of order n, and we characterize the digraphs D with $γ_S(D) + d_S(D) = n + 1$. Some of our theorems imply well-known results on the signed domination number of graphs.},

author = {Lutz Volkmann},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {digraph; oriented graph; signed dominating function; signed domination number; signed domatic number},

language = {eng},

number = {3},

pages = {415-427},

title = {Signed domination and signed domatic numbers of digraphs},

url = {http://eudml.org/doc/270815},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Lutz Volkmann

TI - Signed domination and signed domatic numbers of digraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 3

SP - 415

EP - 427

AB - Let D be a finite and simple digraph with the vertex set V(D), and let f:V(D) → -1,1 be a two-valued function. If $∑_{x ∈ N¯[v]}f(x) ≥ 1$ for each v ∈ V(D), where N¯[v] consists of v and all vertices of D from which arcs go into v, then f is a signed dominating function on D. The sum f(V(D)) is called the weight w(f) of f. The minimum of weights w(f), taken over all signed dominating functions f on D, is the signed domination number $γ_S(D)$ of D. A set ${f₁,f₂,...,f_d}$ of signed dominating functions on D with the property that $∑_{i = 1}^d f_i(x) ≤ 1$ for each x ∈ V(D), is called a signed dominating family (of functions) on D. The maximum number of functions in a signed dominating family on D is the signed domatic number of D, denoted by $d_S(D)$. In this work we show that $4-n ≤ γ_S(D) ≤ n$ for each digraph D of order n ≥ 2, and we characterize the digraphs attending the lower bound as well as the upper bound. Furthermore, we prove that $γ_S(D) + d_S(D) ≤ n + 1$ for any digraph D of order n, and we characterize the digraphs D with $γ_S(D) + d_S(D) = n + 1$. Some of our theorems imply well-known results on the signed domination number of graphs.

LA - eng

KW - digraph; oriented graph; signed dominating function; signed domination number; signed domatic number

UR - http://eudml.org/doc/270815

ER -

## References

top- [1] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs, Graph Theory, Combinatorics, and Applications, John Wiley and Sons, Inc. 1 (1995) 311-322. Zbl0842.05051
- [2] M.A. Henning and P.J. Slater, Inequalities relating domination parameters in cubic graphs, Discrete Math. 158 (1996) 87-98, doi: 10.1016/0012-365X(96)00025-8. Zbl0858.05058
- [3] H. Karami, S.M. Sheikholeslami and A. Khodkar, Lower bounds on the signed domination numbers of directed graphs, Discrete Math. 309 (2009) 2567-2570, doi: 10.1016/j.disc.2008.04.001. Zbl1211.05117
- [4] M. Sheikholeslami and L. Volkmann, Signed domatic number of directed graphs, submitted. Zbl06187634
- [5] L. Volkmann and B. Zelinka, Signed domatic number of a graph, Discrete Appl. Math. 150 (2005) 261-267, doi: 10.1016/j.dam.2004.08.010. Zbl1079.05071
- [6] B. Zelinka, Signed domination numbers of directed graphs, Czechoslovak Math. J. 55 (2005) 479-482, doi: 10.1007/s10587-005-0038-5. Zbl1081.05042
- [7] Z. Zhang, B. Xu, Y. Li and L. Liu, A note on the lower bounds of signed domination number of a graph, Discrete Math. 195 (1999) 295-298, doi: 10.1016/S0012-365X(98)00189-7. Zbl0928.05052

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.