The minimum number of maximal dissociation sets in unicyclic graphs

Abstract

A subset of vertices in a graph $G$ is considered a maximal dissociation set if it induces a subgraph with vertex degree at most 1 and it is not contained within any other dissociation sets. In this paper, it is shown that for $n\ge 3$, every unicyclic graph contains a minimum of $\lfloor n/2\rfloor +2$ maximal dissociation sets. We also show the graphs that attain this minimum bound.

13 pages, 7 figures