Title of article
Almost all cop-win graphs contain a universal vertex
Author/Authors
Bonato، نويسنده , , Anthony and Kemkes، نويسنده , , Graeme and Pra?at، نويسنده , , Pawe?، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2012
Pages
6
From page
1652
To page
1657
Abstract
We consider cop-win graphs in the binomial random graph 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 n is equal to ( 1 + o ( 1 ) ) n 2 n 2 / 2 − 3 n / 2 + 1 .
Keywords
Cop-win graph , random graphs , Cop-win ordering , Universal vertex
Journal title
Discrete Mathematics
Serial Year
2012
Journal title
Discrete Mathematics
Record number
1599965
Link To Document