4-cop-win graphs have at least 19 vertices

DOI10.1016/J.DAM.2021.05.012MaRDI QIDQ2032980zbMATH OpenOpenAlexFDO

Authors Jérémie Turcotte, Samuel Yvon

Publication date 14 June 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.02998

zbMATH Keywords

4-cop-wincomputer-assisted proofcop numbercops and robbersextremal problemsgraph construction

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: We show that the cop number of any graph on 18 or fewer vertices is at most 3. This answers a question posed by Andreae in 1986, as well as more recently by Baird et al. We also find all 3-cop-win graphs on 11 vertices, narrow down the possible 4-cop-win graphs on 19 vertices and make some progress on finding the minimum order of 3-cop-win planar graphs.

Recommendations

• On the minimum order of k-cop-win graphs
• On the conjecture of the smallest 3-cop-win planar graph
• A game of cops and robbers
• A better bound for the cop number of general graphs
• On the cop number of a graph

Cites work

• A bound for the cops and robbers problem
• A game of cops and robbers
• A note on \(k\)-cop-win graphs
• Characterizations of k-copwin graphs
• Conjectures on cops and robbers
• Cops and robbers from a distance
• Cops and robbers in graphs with large girth and Cayley graphs
• Julia: a fresh approach to numerical computing
• Meyniel's conjecture on the cop number: a survey
• On a pursuit game on Cayley graphs
• On a pursuit game played on graphs for which a minor is excluded
• On Meyniel's conjecture of the cop number
• On the conjecture of the smallest 3-cop-win planar graph
• On the cop number of a graph
• On the cop number of toroidal graphs
• On the minimum order of k-cop-win graphs
• Practical graph isomorphism. II.
• The game of cops and robbers on graphs
• The smallest graph of girth 5 and valency 4
• Topological directions in cops and robbers
• Variations on cops and robbers
• Vertex-to-vertex pursuit in a graph

Cited in

(5)

• On the conjecture of the smallest 3-cop-win planar graph
• Almost all cop-win graphs contain a universal vertex
• On the minimum order of 4-lazy cops-win graphs
• On the minimum order of k-cop-win graphs
• COP numbers of periodic graphs

Describes a project that uses

Uses Software

• nauty
• Traces
• Julia
• Cop-Number
• Mathematica
• LightGraphs.jl
• GitHub

This page was built for publication: 4-cop-win graphs have at least 19 vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032980)