Trees with Maximum p-Reinforcement Number

الأصل · EN

Let G=(V,E) be a graph and p a positive integer. The p-domination number ₚ(G) is the minimum cardinality of a set D V with |NG(x)∩ D|≥ p for all x∈ V D. The p-reinforcement number rₚ(G) is the smallest number of edges whose addition to G results in a graph G' with ₚ(G')<ₚ(G). Recently, it was proved by Lu et al. that rₚ(T)≤ p+1 for a tree T and p≥ 2. In this paper, we characterize all trees attaining this upper bound for p≥ 3.