We explore connections between brightest cluster galaxies (BCGs) and their host clusters. We first construct a HeCS-omnibus cluster sample including 227 galaxy clusters within 0.02<z<0.30; the total number of spectroscopic members from MMT/Hectospec and SDSS observations is 52325. Taking advantage of the large spectroscopic sample, we compute physical properties of the clusters including the dynamical mass and cluster velocity dispersion ({sigma}_cl_). We also measure the central stellar velocity dispersion of the BCGs ({sigma}_*,BCGs_) to examine the relation between BCG velocity dispersion and cluster velocity dispersion for the first time. The observed relation between BCG velocity dispersion and the cluster velocity dispersion is remarkably tight. Interestingly, the {sigma}_*,BCG_/{sigma}_cl_ ratio decreases as a function of {sigma}_cl_ unlike the prediction from the numerical simulation of Dolag+ (2010MNRAS.405.1544D). The trend in {sigma}_*,BCG_/{sigma}_cl_ suggests that BCG formation is more efficient in lower mass halos.