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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Aug 16, 2012 at 5:02
  • 2
    $\begingroup$ Have you asked the contest authors about it? $\endgroup$
    – Zack Wolske
    Commented Aug 16, 2012 at 5:53
  • $\begingroup$ Thanks to Gerhard Paseman and Gerry Myerson for getting us on the right track. @Zack Wolske - Yes. $\endgroup$
    – Ken Monks
    Commented Aug 20, 2012 at 22:20

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .