Quasi-Tree Graphs with the Second Largest Number of Maximal Independent Sets

Abstract

A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) $G$ with vertex set $V(G)$ is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex $x\in V(G)$ such that $G–x$ is a tree (respectively, forest). In this paper, we determine the second largest numbers of maximal independent sets among all quasi-tree graphs and quasi-forest graphs. We also characterize those extremal graphs achieving these values.