Almost all \(k\)-cop-win graphs contain a dominating set of cardinality \(k\)

DOI10.1016/j.disc.2014.08.023zbMath1302.05172arXiv1305.1676OpenAlexW2963210532MaRDI QIDQ468433

Paweł Prałat

Publication date: 7 November 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.1676

zbMATH Keywords

random graphs\(k\)-cop-win graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Characterizations of \(k\)-copwin graphs
• Almost all cop-win graphs contain a universal vertex
• A game of cops and robbers
• Vertex-to-vertex pursuit in a graph
• Cops and robbers in a random graph
• Meyniel's conjecture holds for random graphs
• Chasing robbers on random graphs: Zigzag theorem
• Pursuit-Evasion in Models of Complex Networks
• Unnamed Item
• Unnamed Item
• Unnamed Item

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