Article ID Journal Published Year Pages File Type
4648138 Discrete Mathematics 2012 4 Pages PDF
Abstract

A kk-dominating set in a graph GG is a set SS of vertices such that every vertex of GG is at distance at most kk from some vertex of SS. Given a class DD of finite simple graphs closed under connected induced subgraphs, we completely characterize those graphs GG in which every connected induced subgraph has a connected kk-dominating subgraph isomorphic to some D∈DD∈D. We apply this result to prove that the class of graphs hereditarily DD-dominated within distance kk 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 DD is dropped.

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