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 i n 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 c h o o s e k 2^{n^{2} / 2 - (1 / 2 - l o g_{2} (1 - 2^{- k})) n}

.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: Almost all \(k\)-cop-win graphs contain a dominating set of cardinality \(k\)