Exponential Independence Number of Some Graphs
Articles > Article · 2018
Authors: Canan Ciftci, Aysun AYTAÇ
International Journal of Foundations of Computer Science, Journal Indexed in SCI Expanded, International, WoS, 2018, vol 29, pp 1151-1164
DOI: 10.1142/s0129054118500260
Summary
Let [Formula: see text] be a graph and [Formula: see text]. We define by [Formula: see text] the subgraph of [Formula: see text] induced by [Formula: see text]. For each vertex [Formula: see text] and for each vertex [Formula: see text], [Formula: see text] is the length of the shortest path in [Formula: see text] between [Formula: see text] and [Formula: see text] if such a path exists, and [Formula: see text] otherwise. For a vertex [Formula: see text], let [Formula: see text] where [Formula: see text]. Jäger and Rautenbach [27] define a set [Formula: see text] of vertices to be exponential independent if [Formula: see text] for every vertex [Formula: see text] in [Formula: see text]. The exponential independence number [Formula: see text] of [Formula: see text] 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.