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