Nonlocality of Cover-Time Changes Under Edge Addition
Let $G$ be a finite connected simple graph, let $uv$ be a nonedge, and let $s$ be a starting vertex. We study the exact change in the expected cover time of simple random walk when $uv$ is inserted. A killed Green matrix update, combined with target-set inclusion-exclusion, gives an exact formula using only the original graph. The response can have either sign. Our main result is a nonlocality theorem. For every radius $r\geq 1$, we construct two marked configurations whose ambient-degree-labelled radius-$r$ neighbourhoods at $s,u,v$ are isomorphic but whose fixed-start cover-time responses…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.27474
curl -X POST /api/v1/records/arxiv/2608.27474/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.27474/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'