The number of 1-nearly independent vertex subsets

AbstractLet 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, σ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 σ1 are provided, as well as some cases of explicit formulas. We prove a tight lower (resp. upper) bound on σ1 for graphs of order n. We deduce as a corollary that the star K1,n−1 (the tree with degree sequence (n − 1, 1, . . . , 1)) is the n-vertex tree with smallest σ1, while it is well known that K1,n−1 is the n-vertex tree with largest number of independent subsets.Mathematics Subject Classification (2020): 05C69Key words: 1-nearly independent vertex subsetminimal connected graphsmaximal graphs