On the signed (total) k-domination number of a graph

Abstract: Let

k

be a positive integer and

G = (V, E)

be a graph of minimum degree at least

k - 1

. A function

f : V i g h t a r r o w - 1, 1

is called a emph{signed

k

-dominating function} of

G

if

s u m_{u i n N_{G} [v]} f (u) g e q k

for all

v i n V

. The emph{signed

k

-domination number} of

G

is the minimum value of

s u m_{v i n V} f (v)

taken over all signed

k

-dominating functions of

G

. The emph{signed total

k

-dominating function} and emph{signed total

k

-domination number} of

G

can be similarly defined by changing the closed neighborhood

N_{G} [v]

to the open neighborhood

N_{G} (v)

in the definition. The emph{upper signed

k

-domination number} is the maximum value of

s u m_{v i n V} f (v)

taken over all emph{minimal} signed

k

-dominating functions of

G

. In this paper, we study these graph parameters from both algorithmic complexity and graph-theoretic perspectives. We prove that for every fixed

k g e q 1

, the problems of computing these three parameters are all NP-hard. We also present sharp lower bounds on the signed

k

-domination number and signed total

k

-domination number for general graphs in terms of their minimum and maximum degrees, generalizing several known results about signed domination.

Recommendations

Cited in

(11)

This page was built for publication: On the signed (total) \(k\)-domination number of a graph