Discrete Math Seminar: Peter Bradshaw

  • Date: 10/15/2019
  • Time: 16:00
Peter Bradshaw, SFU

University of British Columbia


Graphs with high cop number.


We explore classes of graphs on which a large number of pursuers are required to capture an evader. We give a lower bound for the cop number of graphs of high girth that improves a result of P. Frankl. We also consider lower bounds for the cop number of various algebraically constructed graph classes. In particular, we present a class of directed graphs with cop number (1-o(1)) \sqrt{n}, which is greater than any lower bound currently known for any directed graph class.

Other Information: 

Location: ESB 4127