Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421140 | Discrete Applied Mathematics | 2014 | 12 Pages |
Abstract
Let G=(V,E)G=(V,E) be a graph and pp a positive integer. The pp-domination number γp(G)γp(G) is the minimum cardinality of a set D⊆VD⊆V with |NG(x)∩D|≥p|NG(x)∩D|≥p for all x∈V∖Dx∈V∖D. The pp-reinforcement number rp(G)rp(G) is the smallest number of edges whose addition to GG results in a graph G′G′ with γp(G′)<γp(G)γp(G′)<γp(G). It is showed by Lu et al. (2013) that rp(T)≤p+1rp(T)≤p+1 for any tree TT and p≥2p≥2. This paper characterizes all trees attaining this upper bound when p≥3p≥3.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
You Lu, Jun-Ming Xu,