Meyniel's conjecture on the cop number: A survey

被引：0

作者：

Baird, William ^{[1
]}

Bonato, Anthony ^{[1
]}

机构：

[1] Ryerson Univ, Dept Math, Toronto, ON M5B 2K3, Canada

来源：

JOURNAL OF COMBINATORICS | 2012年 / 3卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Cops and robbers; cop number; retract; random graph;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Meyniel's conjecture is one of the deepest open problems on the cop number of a graph. It states that for a connected graph G of order n, c(G) = O(root n). While largely ignored for over 20 years, the conjecture is receiving increasing attention. We survey the origins of and recent developments towards the solution of the conjecture. We present some new results on Meyniel extremal families containing graphs of order n satisfying c(G) >= d root n, where d is a constant.

引用

页码：225 / 238

页数：14