Article ID Journal Published Year Pages File Type
4650681 Discrete Mathematics 2008 11 Pages PDF
Abstract

In this paper, we study a generalization of the paired domination number. Let G=(V,E)G=(V,E) be a graph without an isolated vertex. A set D⊆V(G)D⊆V(G) is a k-distance paired dominating set of G if D is a k-distance dominating set of G   and the induced subgraph 〈D〉〈D〉 has a perfect matching. The k-distance paired domination number  γpk(G) is the cardinality of a smallest k-distance paired dominating set of G. We investigate properties of the k-distance paired domination number of a graph. We also give an upper bound and a lower bound on the k-distance paired domination number of a non-trivial tree T in terms of the size of T and the number of leaves in T and we also characterize the extremal trees.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,