Signed domination and signed domatic numbers of digraphs
Lutz Volkmann
Discussiones Mathematicae Graph Theory, Tome 31 (2011), p. 415-427 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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₂,...,fd of signed dominating functions on D with the property that ∑i=1dfi(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 dS(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)+dS(D)≤n+1 for any digraph D of order n, and we characterize the digraphs D with γS(D)+dS(D)=n+1. Some of our theorems imply well-known results on the signed domination number of graphs.

Publié le : 2011-01-01
EUDML-ID : urn:eudml:doc:270815 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1555,
     author = {Lutz Volkmann},
     title = {Signed domination and signed domatic numbers of digraphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {31},
     year = {2011},
     pages = {415-427},
     zbl = {1227.05207},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1555}
}

Lutz Volkmann. Signed domination and signed domatic numbers of digraphs. Discussiones Mathematicae Graph Theory, Tome 31 (2011) pp. 415-427. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1555/

[000] [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. | Zbl 0842.05051

[001] [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. | Zbl 0858.05058

[002] [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. | Zbl 1211.05117

[003] [4] M. Sheikholeslami and L. Volkmann, Signed domatic number of directed graphs, submitted. | Zbl 06187634

[004] [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. | Zbl 1079.05071

[005] [6] B. Zelinka, Signed domination numbers of directed graphs, Czechoslovak Math. J. 55 (2005) 479-482, doi: 10.1007/s10587-005-0038-5. | Zbl 1081.05042

[006] [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. | Zbl 0928.05052