{"id":"arxiv/2610.35408","url":"https://arxiv.org/abs/2610.35408","tags":["math.CO"],"score":0,"title":"A characterization of graphs attaining a lower bound on the dissociation number","domain":"math.CO","source":"arxiv","authors":["Pingshan Li"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-26","reactions":{}}