The number of $1$-nearly independent vertex subsets

Abstract

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. A subset $I$ of $V(G)$ is an independent vertex subset if no two vertices in $I$ are adjacent in $G$. We study the number, ${\sigma }_1(G)$, of all subsets of $v(G)$ that contain exactly one pair of adjacent vertices. We call those subsets 1-nearly independent vertex subsets. Recursive formulas of ${\sigma }_1$ are provided, as well as some cases of explicit formulas. We prove a tight lower (resp. upper) bound on ${\sigma }_1$ for graphs of order $n$. We deduce as a corollary that the star $K_{1,n-1}$ (the tree with degree sequence $(n-1,1,\dots ,1)$) is the $n$-vertex tree with smallest ${\sigma }_1$, while it is well known that $K_{1,n-1}$ is the $n$-vertex tree with largest number of independent subsets.

21 pages, 3 tables