Probability model of connectedness for graphs with logarithmical degree

For a graph G of order N, an integer k with 0≤ k< N and a real number p with 0≤ p≤ 1, let $p(G,k)$ and $t(G,p)$ be the probabilities that G is disconnected when k vertices are removed randomly and when each vertex is removed independently with probability p, respectively. We deduce a formula of $p(G,k)$ for Harary graphs and show that the phase transition on $p(G,k)$ and $t(G,p)$ occurs in the class that has logarithmical degree. We also perform simulations on $p(G,k)$ for the Hypercube and randomly generated graphs of the same scale, which suggests that the regularity is a key structural feature that guarantees nice performance on $p(G,k)$. In particular, the Hypercubes have better performance than regular graphs, on average. Surprisingly, Harary graphs, known to be super-connected, have neither better performance than Hypercubes nor even than the average of regular graphs.