A better bound for the cop number of general graphs |
| |
| Authors: | Ehsan Chiniforooshan |
| |
| Institution: | School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 |
| |
| Abstract: | In this note, we prove that the cop number of any n‐vertex graph G, denoted by  , is at most  . Meyniel conjectured  . It appears that the best previously known sublinear upper‐bound is due to Frankl, who proved  . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 45–48, 2008 |
| |
| Keywords: | graph caterpillar cops and robbers search number |
|
|
