Upper signed domination number |
| |
Authors: | Huajun Tang |
| |
Institution: | a Department of Logistics, The Hong Kong Polytechnic University, Hung Kom, Kowloon, Hong Kong, PR China b Department of Mathematics, Nanjing University, Nanjing 210093, PR China |
| |
Abstract: | Let G=(V,E) be a graph. A signed dominating function on G is a function f:V→{-1,1} such that for each v∈V, where Nv] is the closed neighborhood of v. The weight of a signed dominating function f is . A signed dominating function f is minimal if there exists no signed dominating function g such that g≠f and g(v)?f(v) for each v∈V. The upper signed domination number of a graph G, denoted by Γs(G), equals the maximum weight of a minimal signed dominating function of G. In this paper, we establish an tight upper bound for Γs(G) in terms of minimum degree and maximum degree. Our result is a generalization of those for regular graphs and nearly regular graphs obtained in O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287-293] and C.X. Wang, J.Z. Mao, Some more remarks on domination in cubic graphs, Discrete Math. 237 (2001) 193-197], respectively. |
| |
Keywords: | Upper bound Upper signed domination number |
本文献已被 ScienceDirect 等数据库收录! |
|