Optimal Graphs for Connectedness under Random Edge Deletion

Abstract

Performing percolation on a finite graph G means independently keeping or discarding each edge according to a probability parameter p. The focus is the probability Pc(G, p) that a percolation outcome turns out to be a connected graph. Specifically, if we fix p, the number of vertices n and the number of edges m, we try to find the graph(s) with the highest such probability. We call such graphs the most stable or the (n, m, p)-optimal graphs. It is shown that any (n, m, p)-optimal graph consists of a single so-called block. For m = n, m = n + 1 and m = n + 2 respectively, we show the existence of a unique optimal graph, which is actually independent of p. However, in general, the relative stability of two (n,m)-graphs is p-dependent. We make some investigations into when this is the case.