A characterization of graphs attaining a lower bound on the dissociation number
Abstract
The dissociation number diss(G) of a graph G is defined as the maximum cardinality of a vertex subset D⊆ 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 diss(G)≥ n−1/3(m+k+c1) where n, m, k, c1 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.
Related
- Characterization of graphs attaining the maximum signless Laplacian spectral radius under forbidden cycles and theta graphs
- Minimizing the spectral radius of unicyclic graphs with fixed order and dissociation number
- Exponential Lower Bounds for the Pfaffian Number of Graphs
- Explicit lower bounds on the conductors of elliptic curves and abelian varieties over number fields
- An improved lower bound for the packing number of the 2-token graph of the cycle
BibTeX
@misc{li2026characterization,
title = {{A characterization of graphs attaining a lower bound on the dissociation number}},
author = {Pingshan Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35408},
eprint = {2610.35408},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35408},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A characterization of graphs attaining a lower bound on the dissociation number
AU - Pingshan Li
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35408
UR - https://arxiv.org/abs/2610.35408
AB - The dissociation number diss(G) of a graph G is defined as the maximum cardinality of a vertex subset D⊆ 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 diss(G)≥ n−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.
ER -