The Large Numbers of \(2\)-Independent Sets in Extra-Free Forests

Abstract

A 2-independent set in a graph \(G\) is a subset \(J\) of the vertices such that the distance between any two vertices of \(J\) in \(G\) is at least three. The number of 2-independent sets of a graph \(G\) is denoted by \(i_2(G)\). For a forest \(F\), \(i_2(F – e) > i_2(F)\) for each edge \(e\) of \(F\). Hence, we exclude all forests having isolated vertices. A forest is said to be extra-free if it has no isolated vertex. In this paper, we determine the \(k\)-th largest number of 2-independent sets among all extra-free forests of order \(n \geq 2\), where \(k = 1, 2, 3\). Extremal graphs achieving these values are also given.