Almost all cop-win graphs contain a universal vertex

作者：Bonato Anthony; Kemkes Graeme; Pralat Pawel^*

来源：Discrete Mathematics, 2012, 312(10): 1652-1657.

DOI：10.1016/j.disc.2012.02.018

• Cop-win graph
• Random graphs
• Universal vertex
• Cop-win ordering

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)) n2(n2/2-3n/2+1).

• 出版日期2012-5-28