k- and k-stable graphs

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. c 2000 Elsevier Science B.V. All rights reserved.