Premium
On Meyniel's conjecture of the cop number
Author(s) -
Lu Linyuan,
Peng Xing
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20642
Subject(s) - combinatorics , mathematics , conjecture , bipartite graph , upper and lower bounds , graph , constant (computer programming) , discrete mathematics , computer science , mathematical analysis , programming language
Meyniel conjectured that the cop number c ( G ) of any connected graph G on n vertices is at most for some constant C . In this article, we prove Meyniel's conjecture in special cases that G has diameter 2 or G is a bipartite graph of diameter 3. For general connected graphs, we prove , improving the best previously known upper‐bound O ( n / ln n ) due to Chiniforooshan.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom