2017/02/01 by Davood Bakhshesh, Mohammad Farshi, Bakhshesh, Davood +3
Computer Science · Mathematics · #05C69 #68Q25 #68R05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1702.00533
openalex publication_date 2017/02/01 · openalex created_date 2022/09/02 · openalex updated_date 2026/07/28
Let G=(V, E) be a simple and undirected graph. For some integer k\≥ 1,\na set D\⊆ V is said to be a k-dominating set in G if every vertex\nv of G outside D has at least k neighbors in D. Furthermore, for some\nreal number \α with 0<\α\≤1, a set D\⊆ V is called an\n\α-dominating set in G if every vertex v of G outside D has at\nleast \α\× dv neighbors in D, where dv is the degree of v in\nG. The cardinality of a minimum k-dominating set and a minimum\n\α-dominating set in G is said to be the k-domination number and the\n\α-domination number of G, respectively. In this paper, we present some\napproximability and inapproximability results on the problem of finding\nk-domination number and \α-domination number of some classes of graphs.\nMoreover, we introduce a generalization of \α-dominating set which we\ncall an f-dominating set. Given a function f:\ℕ\→\n\ℝ, where \ℕ= 1, 2, 3, \… , a set D\⊆ V is\nsaid to be an f-dominating set in G if every vertex v of G outside D\nhas at least f(dv) neighbors in D. We prove NP-hardness of the problem of\nfinding a minimum f-dominating set in G, for a large family of functions\nf.\n