Relating the independence number and the dissociation number

Abstract

The independence number $\alpha (G)$ and the dissociation number $\mathrm{diss}(G)$ of a graph $G$ are the largest orders of induced subgraphs of $G$ of maximum degree at most $0$ and at most $1$, respectively. We consider possible improvements of the obvious inequality $2\alpha (G)\ge \mathrm{diss}(G)$. For connected cubic graphs $G$ distinct from $K_4$, we show $5\alpha (G)\ge 3\mathrm{diss}(G)$, and describe the rich and interesting structure of the extremal graphs in detail. For bipartite graphs, and, more generally, triangle-free graphs, we also obtain improvements. For subcubic graphs though, the inequality cannot be improved in general, and we characterize all extremal subcubic graphs.