On the average size of $1$-nearly independent vertex sets in graphs

Abstract

A $k$-nearly independent vertex subset of a graph $G$ is a set of vertices that induces a subgraph containing exactly $k$ edges. For $k=0$, this coincides with the classical notion of independent subsets. This paper investigates the average size, $a{v}_1(G)$ of the $1$-nearly independent vertex subsets of both graphs and trees of a given order $n$. Let $E_n$ denote the $n$-vertex edgeless graph, so that $a{v}_1(E_n)=0$. We determine all $n$-vertex graphs $G\ne E_n$ that minimize or maximize $a{v}_1$. Similarly, we identify the trees of order $n$ that achieve the minimum value of $a{v}_1$, and prove that the maximum value lies between $n/2$ and $(n+1)/2$ if $n>8$. Finally, we construct a family of $n$-vertex trees which shows that the bounds are asymptotically sharp.

13 pages