Discussiones Mathematicae Graph Theory 31(3) (2011)
415-427
doi: 10.7151/dmgt.1555
Lutz Volkmann
Lehrstuhl II für Mathematik
RWTH-Aachen University
52056 Aachen, Germany
e-mail: volkm@math2.rwth-aachen.de
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.
Keywords: digraph, oriented graph, signed dominating function, signed domination number, signed domatic number.
2010 Mathematics Subject Classification: 05C69.
[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. |
[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. |
[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 . |
[4] | M. Sheikholeslami and L. Volkmann, Signed domatic number of directed graphs, submitted. |
[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. |
[6] | B. Zelinka, Signed domination numbers of directed graphs, Czechoslovak Math. J. 55 (2005) 479-482, doi: 10.1007/s10587-005-0038-5. |
[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. |
Received 29 January 2010
Revised 26 April 2010
Accepted 27 April 2010