αk- and γk-stable graphs Original Research Article

A set I of vertices of a graph G is k-independent if the distance between every two vertices of I is at least k+1. The k-independence number, αk(G), is the cardinality of a maximum k-independent set of G. A set D of vertices of G is k-dominating if every vertex in V(G)−D is at distance at most k from some vertex in D. The k-domination number, γk(G), is the cardinality of a minimum k-dominating set of G. A graph G is αk-stable (γk-stable) if αk(G−e)=αk(G) (γk(G−e)=γk(G)) for every edge e of G. We establish conditions under which a graph is αk- and γk-stable. In particular, we give constructive characterizations of αk- and γk-stable trees.