Almost all k-cop-win graphs contain a dominating set of cardinality k

Abstract

We consider $k$-cop-win graphs in the binomial random graph $G(n,1/2).$ It is known that almost all cop-win graphs contain a universal vertex. We generalize this result and prove that for every $k\in N$, almost all $k$-cop-win graphs contain a dominating set of cardinality $k$. From this it follows that the asymptotic number of labelled $k$-cop-win graphs of order $n$ is equal to $(1+o(1))(1-2^{-k}{)}^{-k}(\genfrac{}{}{0ex}{}{n}{k})2^{n^2/2-(1/2-{\log }_2(1-2^{-k}))n}$.

References in corpus (1)

• Meyniel's conjecture holds for random graphs