On the 2-independence subdivision number of graphs

A subset S of vertices in a graph G = (V;E) is 2-independent if every vertexof S has at most one neighbor in S: The 2-independence number is the maximumcardinality of a 2-independent set of G: In this paper, we initiate the study of the2-independence subdivision number sdβ2(G) defined as the minimum numberof edges that must be subdivided (each edge in G can be subdivided at mostonce) in order to increase the 2-independence number. We first show that forevery connected graph G of order at least three, 1≤sdβ2(G)≤2; and we give anecessary and sufficient condition for graphs G attaining each bound. Moreover,restricted to the class of trees, we provide a constructive characterization of alltrees T with sdβ2(T)= 2; and we show that such a characterization suggestsan algorithm that determines whether a tree T has sdβ2(T)= 2 or sdβ2(T) = 1in polynomial time.