A characterization of graphs attaining a lower bound on the dissociation number
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.35408
curl -X POST /api/v1/records/arxiv/2610.35408/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.35408/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'