Can I read Almost All K-cop-win Graphs Contain a Dominating Set of Cardinality K on EtoBox?

Almost All K-cop-win Graphs Contain a Dominating Set of Cardinality K by Pralat, Pawel is a scholarly article available to read on EtoBox.

What is Almost All K-cop-win Graphs Contain a Dominating Set of Cardinality K about?

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} {n \choose k} 2^{n^2/2 - (1/2-\log_2(1-2^{-k})) n}$.

Author

Pralat, Pawel

Published

2013

Language

EN