<p>The graph reliability is the probability that a connected graph remains connected after the removal of a random number of its vertices or edges. In this article, the problem addressed is identifying the topological change in a graph that leads to the greatest increase in its graph reliability. We restrict our domain to a subproblem consisting of the case in which removal occurs only on the vertices of a graph (vertex reliability), and the only topological change allowed is a single edge insertion. In this setting, we describe 6 heuristics, all previously used in the context of edge reliability or other robustness measures. Specifically, we further analyze two spectral heuristics and their theoretical motivations with respect to vertex reliability. The performance of these 6 heuristics is evaluated by a set of computational experiments with 22000 graphs of orders 10 up to 20, generated using the Erdős-Rényi, Barabási-Albert, and Watts-Strogatz models, that compared the vertex reliability of each edge insertion produced by the heuristics. From the experiments, one spectral heuristic presented a superior performance <i>versus</i> the others. We propose an explanation for why this spectral heuristic performed so well and how its underlying principle – the Fiedler vector – is intrinsically linked to local and global connectedness information of the graph. Additionally, we present an initial refinement of this spectral heuristic and compare it against the others in order to show potential developments using spectral measures.</p>