  We study network configurations that provide optimal robustness to random
breakdowns for networks with a given number of nodes $N$ and a given
cost--which we take as the average number of connections per node $\kav$. We
find that the network design that maximizes $f_c$, the fraction of nodes that
are randomly removed before global connectivity is lost, consists of
$q=[(\kav-1)/\sqrt\kav]\sqrt N$ high degree nodes (``hubs'') of degree
$\sqrt{\kav N}$ and $N-q$ nodes of degree 1. Also, we show that $1-f_c$
approaches 0 as $1/\sqrt N$--faster than any other network configuration
including scale-free networks. We offer a simple heuristic argument to explain
our results.
