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

作者：Pralat Pawel^*

来源：Discrete Mathematics, 2015, 338(1): 47-52.

DOI：10.1016/j.disc.2014.08.023

• k-cop-win graph
• Random graphs

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 is an element of 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)(k)) 2(n2/2-(1/2-log2(1-2-k))n).

• 出版日期2015-1-6