Title of article :
Distance domination versus iterated domination
Author/Authors :
Bacsَ، نويسنده , , Gلbor and Tuza، نويسنده , , Zsolt، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
Abstract :
A k -dominating set in a graph G is a set S of vertices such that every vertex of G is at distance at most k from some vertex of S . Given a class D of finite simple graphs closed under connected induced subgraphs, we completely characterize those graphs G in which every connected induced subgraph has a connected k -dominating subgraph isomorphic to some D ∈ D . We apply this result to prove that the class of graphs hereditarily D -dominated within distance k is the same as the one obtained by iteratively taking the class of graphs hereditarily dominated by the previous class in the iteration chain. This strong relation does not remain valid if the initial hereditary restriction on D is dropped.
Keywords :
dominating set , Class of connected graphs , Distance domination , forbidden induced subgraph
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics