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\ge 2$, where $k=1,2,3$. Extremal graphs achieving these values are also given.