Probabilistic analysis of upper bounds for 2-connected distance k-dominating sets in graphs

A small virtual backbone which is modeled as the minimum connected dominating set (CDS) problem has been proposed to alleviate the broadcasting storm for efficiency in wireless ad hoc networks. In this paper, we consider a general fault tolerant CDS problem, called an h-connected distance k-dominating set (HCKDS) to balance high efficiency and fault tolerance, and study the upper bound for HCKDS with a probabilistic method for small h and improve the current best results.