Paperlane

no. 13 · Wednesday 11 November 2026

Linear-size graphs at every strict dismantling level

Jesús F. Espinoza, Martín Eduardo Frías-Armenta, Rosalía G. Hernández-Amador and Héctor A. Hernández-Hernández

math.CO · 15 pp

Abstract

Dismantling reduces a graph to one vertex by successive deletions. At level zero, a vertex is eligible if one of its neighbours is adjacent to all its other neighbours. At level $k\geq1$, its neighbours must induce a graph dismantlable at level $k-1$. A graph has strict level $k$ if it admits a reduction at level $k$ and none at level $k-1$. For every $k\geq1$, we construct a graph of strict level $k$ with $3k+8$ vertices. Each step adds three vertices: the neighbours of one induce the preceding graph, and the other two provide the adjacencies used to rule out other first deletions at the lower level. A second construction gives a graph of order $4k+4$ at strict level $k$. Together the two families give the upper bound $\min\{4k+4,3k+8\}$ on the least order at strict level $k$.

comments
15 pages, 3 figures
fields
Combinatorics
pdf ↗ page arXiv:2611.14430 ↗