Trees with Maximum p-Reinforcement Number

2012/11/25 by You Lu, Lu, You, Jun-Ming Xu +1
Mathematics · #05C69 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C69

paper · pdf · doi:10.48550/arxiv.1211.5742

arxiv created 2012/11/25 · arxiv updated 2012/11/27

Abstract

Let G=(V,E) be a graph and p a positive integer. The p-domination number \g_p(G) is the minimum cardinality of a set D⊆ V with |N_G(x)∩ D|≥ p for all x∈ V∖ D. 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')<\g_p(G). Recently, it was proved by Lu et al. that r_p(T)≤ p+1 for a tree T and p≥ 2. In this paper, we characterize all trees attaining this upper bound for p≥ 3.

Related

• On the p-reinforcement and the complexity
• Super domination in trees
• On total domination subdivision numbers of trees
• Complexity of Bondage and Reinforcement
• Trees with Large Neighborhood Total Domination Number