Title of article :
Distance domination versus iterated domination
Author/Authors :
Bacsَ، نويسنده , , Gلbor and Tuza، نويسنده , , Zsolt، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
Pages :
4
From page :
2672
To page :
2675
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
Serial Year :
2012
Journal title :
Discrete Mathematics
Record number :
1600075
Link To Document :
بازگشت