A characterization of graphs attaining a lower bound on the dissociation number

Source abstract

The dissociation number ${\rm diss}(G)$ of a graph $G$ is defined as the maximum cardinality of a vertex subset $D\subseteq V(G)$ such that the induced subgraph $G[D]$ has maximum degree at most $1$. In 2023, Bock, Pardey, Penso and Rautenbach [J. Graph Theory 103 (2023), 661--673] showed that ${\rm diss}(G)\ge n-\frac{1}{3}(m+k+c_1)$ where $n, m, k, c_1$ denote the numbers of vertices, edges, components and induced cycles of length $1$ modulo $3$ in $G$ and they also established a complete characterization of extremal graphs under the vertex-disjoint cycle constraint. Although this partial characterization offers very valuable structural insights, it excludes many simple extremal graphs. So they posed a natural question: How can all extremal graphs be comprehensively characterized without restrictions? In this paper, we give a recursive characterization of all graphs attaining equality in this bound.