Article ID Journal Published Year Pages File Type
419520 Discrete Applied Mathematics 2010 5 Pages PDF
Abstract

Let G=(V,E)G=(V,E) be a simple graph, and let kk be a positive integer. A subset D⊆VD⊆V is a kk-dominating set   of the graph GG if every vertex v∈V−Dv∈V−D is adjacent to at least kk vertices of DD. The kk-domination number  γk(G)γk(G) is the minimum cardinality among the kk-dominating sets of GG. A subset D⊆VD⊆V is said to be a connected  kk-dominating set   if DD is kk-dominating and its induced subgraph is connected. DD is called total  kk-dominating   if every vertex in VV has at least kk neighbors in DD and it is a connected total  kk-dominating set   if, additionally, its induced subgraph is connected. The minimum cardinalities of a connected kk-dominating set, a total kk-dominating set, and a connected total kk-dominating set are respectively denoted as γkc(G), γkt(G) and γkc,t(G). In this paper, we establish different sharp bounds on the connected kk-domination number γkc(G), involving also the parameters γk(G)γk(G), γkt(G) and γkc,t(G).

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,