Almost all cop-win graphs contain a universal vertex

Autor:	Paweł Prałat, Graeme Kemkes, Anthony Bonato
Jazyk:	angličtina
Předmět:	Computer Science::Computer Science and Game Theory 0102 computer and information sciences Computer Science::Human-Computer Interaction 01 natural sciences Theoretical Computer Science Combinatorics Indifference graph Pathwidth Chordal graph Computer Science::Discrete Mathematics Random regular graph Discrete Mathematics and Combinatorics Cograph 0101 mathematics Universal graph Mathematics Random graphs Discrete mathematics Quantitative Biology::Neurons and Cognition Cop-win graph 010102 general mathematics Universal vertex Cop-win ordering 1-planar graph 010201 computation theory & mathematics Maximal independent set
Zdroj:	Discrete Mathematics. (10):1652-1657
ISSN:	0012-365X
DOI:	10.1016/j.disc.2012.02.018
Popis:	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^n^^^2^/^2^-^3^n^/^2^+^1.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::26a4746a1046c26130aeb64c024166d6 Zobrazit plný text záznamu