Maximal and Maximum Dissociation Sets in General and Triangle-Free Graphs

Abstract

A subset of vertices $F$ in a graph $G$ is called a \emph{dissociation set} if the induced subgraph $G[F]$ of $G$ has maximum degree at most 1. A \emph{maximal dissociation set} of $G$ is a dissociation set which is not a proper subset of any other dissociation sets. A \emph{maximum dissociation set} is a dissociation set of maximum size. We show that every graph of order $n$ has at most $10^{\frac{n}{5}}$ maximal dissociation sets, and that every triangle-free graph of order $n$ has at most $6^{\frac{n}{4}}$ maximal dissociation sets. We also characterize the extremal graphs on which these upper bounds are attained. The tight upper bounds on the number of maximum dissociation sets in general and triangle-free graphs are also obtained.