Maximal and maximum dissociation sets in general and triangle-free graphs

In a graph G , a subset of vertices is a dissociation set if it induces a subgraph with maxi-mum degree at most 1 . A maximal dissociation set of G is a dissociation set which is not a proper subset of any other dissociation sets. A maximum dissociation set is a dissocia-tion set of maximum size. We show that every graph of order n has at most 10 n5 maximal dissociation sets, and that every triangle-free graph of order n has at most 6 n4 maximal dissociation sets. We also characterize the extremal graphs on which these upper bounds are attained. (c) 2022 Elsevier Inc. All rights reserved.