On the p-reinforcement and the complexity

2012/04/18 by You Lu, Lu, You, Fu-Tao Hu +3
Computer Science · Engineering · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1204.4013

openalex publication_date 2012/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G=(V,E) be a graph and p be a positive integer. A subset S⊆ V is called a p-dominating set if each vertex not in S has at least p neighbors in S. The p-domination number \g_p(G) is the size of a smallest p-dominating set of G. The p-reinforcement number r_p(G) is the smallest number of edges whose addition to G results in a graph G' with \g_p(G')

Related

• Trees with Maximum p-Reinforcement Number
• Complexity of Bondage and Reinforcement
• On the complexity of the outer-connected bondage and the outer-connected reinforcement problems
• The Algorithmic Complexity of Bondage and Reinforcement Problems in bipartite graphs
• Complexity results for k-domination and \α-domination problems\n and their variants