Step Domination in Graphs

Abstract

A set $S=\{v_1,v_2,\dots ,v_n\}$ of vertices in a graph $G$ with associated sequence $k_1,k_2,\dots ,k_n$ of nonnegative integers is called a step domination set if every vertex of $G$ is at distance $k_i$ from $v_i$ for exactly one $i$ ($1\le i\le n$). The minimum cardinality of a step domination set is called the step domination number of $G$. This parameter is determined for several classes of graphs and is investigated for trees.