A characterization of graphs attaining a lower bound on the dissociation number
math.CO
Submitted: 2026-10-26
Updated: 2026-10-26
Comments: Dissociation sets; dissociation number; maximum; extremal graphs
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
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) at least n-1 over 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.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality