Exponential independence

For a set S of vertices of a graph G, a vertex u in V(G)\S, and a vertex v in S, let dist((G,S))(u, v) be the distance of u and v in the graph G - (S \ {v}). Dankelmann et al. (2009) define S to be an exponential dominating set of G if w((G,S))(u) >= 1 for every vertex u in V(G) \ S, where w((G,S))(u) = Sigma(v is an element of S)(1/2) dist((G,S))((u,v)-1). Inspired by this notion, we define S to be an exponential independent set of G if w((G,S\{u}))(u) < 1for every vertex u in S, and the exponential independence number alpha(e)(G) of G as the maximum order of an exponential independent set of G. Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs G for which alpha(e)(H) equals the independence number a(H) for every induced subgraph H of G, and we give an explicit characterization of all trees T with alpha(e)(T) = alpha(T). (C)2016 Elsevier B.V. All rights reserved.