Article ID Journal Published Year Pages File Type
421140 Discrete Applied Mathematics 2014 12 Pages PDF
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
, ,