The largest number of maximal independent sets in quasi-unicyclic graphs

Abstract

A maximal independent set is an independent set that is not a proper subset of any other independent set. A graph is said to be unicyclic if it contains exactly one cycle. A connected graph (respectively, graph) G with vertex set V(G) is called a connected quasi-unicyclic graph (respectively, quasi-unicyclic graph), if there exists a vertex x V{G) such that G-x is a connected unicyclic (respectively, unicyclic) graph. In this paper, we determine the largest number of maximal independent sets among all connected quasi-unicyclic graphs and quasi-unicyclic graphs. We also characterize those extremal graphs achieving these values. © 2019 Utilitas Mathematica Publishing Inc.. All rights reserved.