Upper signed k-domination in a general graph |
| |
Authors: | Dejan Deli? |
| |
Affiliation: | Department of Mathematics, Ryerson University, Toronto, ON, Canada, M5B 2K3 |
| |
Abstract: | Let k be a positive integer, and let G=(V,E) be a graph with minimum degree at least k−1. A function f:V→{−1,1} is said to be a signed k-dominating function (SkDF) if ∑u∈N[v]f(u)?k for every v∈V. An SkDF f of a graph G is minimal if there exists no SkDF g such that g≠f and g(v)?f(v) for every v∈V. The maximum of the values of ∑v∈Vf(v), taken over all minimal SkDFs f, is called the upper signed k-domination numberΓkS(G). In this paper, we present a sharp upper bound on this number for a general graph. |
| |
Keywords: | Combinatorial problems Signed k-dominating function Minimal signed k-dominating function Upper signed k-domination number |
本文献已被 ScienceDirect 等数据库收录! |
|