Linear-size graphs at every strict dismantling level

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\ge 1$, 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\ge 1$, 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$.

arXiv comment15 pages, 3 figures