Exponential Independence Number of Some Graphs

Abstract

Let G be a graph and S subset of V(G). We define by < S > the subgraph of G induced by S. For each vertex u is an element of S and for each vertex v is an element of S\{u}, d((G, s\{u})())(u,v) is the length of the shortest path in < V(G) - ((S - {u}) - {v})> between u and v if such a path exists, and infinity otherwise. For a vertex u is an element of S, let omega((G, s\{u})) (u) = Sigma (v is an element of s\{u}) (1/2)(d) ((G, s\{u}) (u) (,v)-1) where (1/2)(infinity) = 0. Jager and Rautenbach [27] define a set S of vertices to be exponential independent if omega((G, s\{u})) (u) < 1 for every vertex u in S. The exponential independence number alpha(e)(G) of G is the maximum order of an exponential independent set. In this paper, we give a general theorem and we examine exponential independence number of some tree graphs and thorn graph of some graphs.