An improved lower bound on the number of $1$-nearly independent vertex subsets

Abstract

Let $G=(V(G),E(G))$ be a graph with set of vertices $V(G)$ and set of edges $E(G)$. For $k\ge 0$ an integer, a subset $I_k$ of $V(G)$ is called a $k$-nearly independent vertex subset of $G$ if $I_k$ induces a subgraph of size $k$ in $G$. The number of such subsets in $G$ is denoted by ${\sigma }_k(G)$. In this paper we continue the study of ${\sigma }_1$. In particular, we prove the lower bound on ${\sigma }_1$ for a connected graph that contains a cycle and also characterise the two extremal graphs. This improves the result obtained in [E. O. D. Andriantiana and Z. B. Shozi. The number of 1-nearly independent vertex subsets. \textit{Quaestiones Mathematicae}, accepted].

8 pages