2012/04/21 by Hongyu Liang, Liang, Hongyu
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1204.4827
Accepted by JCMCC
arxiv created 2012/04/21 · openalex publication_date 2012/04/21 · arxiv updated 2012/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let k be a positive integer and G=(V,E) be a graph of minimum degree at least k-1. A function f:V→ \-1,1\ is called a signed k-dominating function of G if ∑u∈ NG[v]f(u)≥ k for all v∈ V. The signed k-domination number of G is the minimum value of ∑v∈ Vf(v) taken over all signed k-dominating functions of G. The signed total k-dominating function and signed total k-domination number of G can be similarly defined by changing the closed neighborhood NG[v] to the open neighborhood NG(v) in the definition. The upper signed k-domination number is the maximum value of ∑v∈ Vf(v) taken over all 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≥ 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.