Let G be a finite connected simple graph with vertex set V(G) and edge set E(G). A function f:V(G) → {1,1} is a signed dominating function if for every vertex v∈V(G), the closed neighborhood of v contains more vertices with function values 1 than with −1. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. In this paper, we calculate The signed domination numbers of the Cartesian product of two paths Pm and Pn for m = 3, 4, 5 and arbitrary n.
References
[1]
Dunbar, J., Hedetniemi, S.T., Henning, M.A. and Slater, P.J. (1995) Signed Domination in Graphs. In: Graph Theory, Combinatorics and Applications, John Wiley & Sons, New York, 311-322.
[2]
Broere, I., Hattingh, J.H., Henning, M.A. and McRae, A.A. (1995) Majority Domination in Graphs. Discrete Mathematics, 138, 125-135.
https://doi.org/10.1016/0012-365X(94)00194-N
[3]
Cockayne, E.J. and Mynhardt, C.M. (1996) On a Generalization of Signed Dominating Functions of Graphs. Ars Combinatoria, 43, 235-245.
[4]
Favaron, O. (1996) Signed Domination in Regular Graphs. Discrete Mathematics, 158, 287-293. https://doi.org/10.1016/0012-365X(96)00026-X
[5]
Haasa, R. and Wexlerb, T.B. (2004) Signed Domination Numbers of a Graph and Its Complement. Discrete Mathematics, 283, 87-92.
https://doi.org/10.1016/j.disc.2004.01.007
[6]
Hosseini, S.M. (2015) New Bounds on the Signed Domination Numbers of Graphs. Australasian Journal of Combinatorics, 61, 273-280.
