{"id":"arxiv/2611.14430","url":"https://arxiv.org/abs/2611.14430","tags":["math.CO","cs.CG","cs.GR"],"score":0,"title":"Linear-size graphs at every strict dismantling level","domain":"math.CO","source":"arxiv","authors":["Jesús F. Espinoza","Martín Eduardo Frías-Armenta","Rosalía G. Hernández-Amador","Héctor A. Hernández-Hernández"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{}}