arXiv:2611.14430 · v1

Linear-size graphs at every strict dismantling level

每个严格拆解层级上的线性规模图

首次提交 2026-11-11 02:05

版本更新 2026-11-11 02:05

雷达观测 2026-11-11 13:07

摘要

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$.

作者备注：15 pages, 3 figures