Linear-size graphs at every strict dismantling level
Source: arxiv.org/abs/2611.14430
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.14430
curl -X POST /api/v1/records/arxiv/2611.14430/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.14430/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'