4
$\begingroup$

The definition of the Workday Number of a finite graph is given on page 14 in http://www.arml.com/2012_contest/2012_Contest_Final_Version.pdf and the rest of the problem statement is given at the top of page 12 (omitted here for brevity). Is the general problem of computing the Workday Number of an arbitrary graph based on a well-known area of graph theory, perhaps under another name? Are there references that would show how results about the Workday Number of an arbitrary finite graph fit into the current research literature in graph theory? i.e. if such results for arbitrary graphs are new or already known?

I coach an exceptionally talented ARML student who has some nice general results about Workday Numbers that go well beyond the contest questions and would like to advise him on how to best write up his results.

$\endgroup$
  • $\begingroup$ For some reason I cannot get a clean copy of the pdf. It seems though that it is related to a Cops and Robbers game, which has been well studied in the computer science literature under that name. Find a few papers on the arXiv about it, and use their bibliographies. Gerhard "Ask Me About System Design" Paseman, 2012.08.15 $\endgroup$ – Gerhard Paseman Aug 16 '12 at 5:02
  • 2
    $\begingroup$ Have you asked the contest authors about it? $\endgroup$ – Zack Wolske Aug 16 '12 at 5:53
  • $\begingroup$ Thanks to Gerhard Paseman and Gerry Myerson for getting us on the right track. @Zack Wolske - Yes. $\endgroup$ – Ken Monks Aug 20 '12 at 22:20
4
$\begingroup$

Maybe a good place to start is Anthony Bonato and Richard J. Nowakowski, The game of cops and robbers on graphs, which is Volume 61 in the Student Mathematical Library, published by the American Mathematical Society, Providence, RI, 2011, ISBN: 978-0-8218-5347-4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.