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, σ ₁(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 σ ₁ are provided, as well as some cases of explicit formulas. We prove a tight lower (resp. upper) bound on σ ₁ 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, . . . , 1)) is the n-vertex tree with smallest σ ₁, while it is well known that K_1,n−1 is the n-vertex tree with largest number of independent subsets.