Article ID Journal Published Year Pages File Type
4648093 Discrete Mathematics 2012 6 Pages PDF
Abstract

We consider cop-win graphs in the binomial random graph G(n,1/2)G(n,1/2). We prove that almost all cop-win graphs contain a universal vertex. From this result, we derive that the asymptotic number of labelled cop-win graphs of order nn is equal to (1+o(1))n2n2/2−3n/2+1(1+o(1))n2n2/2−3n/2+1.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Almost all cop-win graphs contain a universal vertex
Authors
, , ,