Cops and Robbers on Graphs Based on Designs. Issue 9 (17th October 2012)

• Record Type: Journal Article
• Authors: Bonato, Anthony; Burgess, Andrea
• Is Part Of: Journal of combinatorial designs. Volume 21:Issue 9(2013:Sep.)
• Page Start: 404
• Page End: 418
• Publication Date: 2012-10-17
• Subjects: Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21331
• Languages: English
• ISSNs: 1063-8539

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>We investigate the cop number of graphs based on combinatorial designs. Incidence graphs, point graphs, and block intersection graphs are studied, with an emphasis on finding families of graphs with large cop number. We generalize known results on Meyniel extremal families by supplying bounds on the incidence graphs of transversal designs, certain <italic>G</italic>‐designs, and BIBDs with <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t2821v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21331:jcd21331-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>λ</mml:mi><mml:mo>≥</mml:mo><mml:mn>1</mml:mn><mml:mo>.</mml:mo></mml:mrow></mml:math> Families of graphs with diameter 2, <italic>C</italic>₄‐free, and with unbounded chromatic number are described with the conjectured asymptotically maximum cop number.</p> </abstract>