Quasi-Tree Graphs with the Largest and the Second Largest Numbers of Maximum Independent Sets

Abstract

In a graph $G=(V,E)$, an independent set is a subset $I$ of $V(G)$ such that no two vertices in $I$ are adjacent. A maximum independent set is an independent set of maximum size. 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 study the problem of determining the largest and the second largest numbers of maximum independent sets among all quasi-tree graphs and quasi-forest graphs. Extremal graphs achieving these values are also given.