Data and code complement - 4-cop-win graphs have at least 19 vertices

Jérémie Turcotte and Samuel Yvon

The preprint of the article is available on arXiv. If you find a mistake or are able to confirm any of the data below, or for any other inquiries, please contact us by email. We are happy to help anyone who has questions about any part of the article.

General considerations

This page contains all the data referenced in the article. The code used to generate this data is all available on GitHub.

In general, we have tried to split up the computations in pieces as much as possible. This way, it is easier to verify the results by looking at some samples, and if there are mistakes to only recompute the affected data. For example, when computing the cop numbers of graphs on 10 vertices, instead of giving the complete breakdown, we break the graphs into 1000 files and provide the cop number breakdown for each of these files. Sometimes, one process is not sufficient to compute all cases, in which case we aggregate all the results files in a compressed folder (.zip). When these are results that we will use later on in other computations, we also provide a merged file of these results.

For almost all computations, the data also contains the computation time. Computations were done on various computers with different specifications, using varying number of cores and often simulatenously as other processes. Thus, comparing the computation time between two different files is not recommended. The computation times here should be seen in relative terms, not as an exact timing for how long running one of the codes will take on your computer.

The computations were either done on the Université de Montréal - Département de mathématiques et de statistique computer network, or on our personnal computers.

As some tables on this page are very large, and depending on your screen width, you may need to use horizontal scrolling on the table to access all data.

Graph generation

Graph generation in the next few sections is done using Brendan McKay's geng function provided with the nauty/Traces package (version 26r12). A simple Python code to call geng to generate all connected graphs with given properties split in a chosen number of files is available here. For ease of access, we make available here all generated graphs. All graph files will be in graph6 format.

Cop number algorithm

Verification of the cop number is done using this code. The algorithm is inspired from those suggested, for example, in this article, this article and this thesis.

We note that some of the computations were done on a previous version of the code, which had a small bug. Precisely, with it's logic, it would yield that if every set of at most k vertices (playing with k cops) is a dominating set, then the cop number is infinite. It is easy to see that the only graphs with this property are the complete graphs. To fix this problem, a verification of wether the graph contains a dominating set of size k was added at the beginning of the functions. The reason for this bug was that our implementation only tests for a winning line in the matrix (which corresponds to a starting position for the cops for which any choice of initial position for the robber can be won, our criterion for determinining if the graph has cop number at most k) when there is a change in the matrix. When every single possible starting position is trivially winning, then there is never any change in the matrix, which explains this bug. Anyways, the only case in which we calculate the cop number of a complete graph is in the testing phase.

The results files include one line for every graph file. The first number on every line is the file number, and each subsequent number is the number of graphs of given cop number. For instance, the line "8080 2 16744 6 0" indicates that file 8080 contains 2 cop-win graphs, 16744 2-cop-win graphs and 6 3-cop-win graphs. In some files, the number is 4-cop-win number is omitted. In general, we will also save the list of graphs which are 3- or 4-cop-win.

Testing the cop number algorithm

To verify that the algorithms are well implemented, we verify the cop numbers on connected graphs containing between 2 and 10 vertices by comparing with the results presented in this article.

We notice that all counts are identical, except in the case of 10 vertices. In this case, our count of cop-win graphs is 1 more than that of the article. To confirm our count, another computation was done using the equivalence between dismantlable and cop-win graphs. The code is available here (it is rather inefficient and slow) and the counts are available here. Furthermore, the implementation of a general cop number algorithm here also agrees on our counts for cop-win on 10 vertices.

Cop number of some graphs on 11-14 vertices

We present here the results of computing the cop numbers for connected graphs on 11-14 vertices with maximum degree at most 4 or 5.

Cop number of subcubic graphs

We present here the results of computing the cop numbers of connected graphs on 10-20 vertices where the minimum degree is at least 2 and the maximum degree is at most 3.

The subcubic 3-cop-win graphs which are also planar can then be found using this code.

Building and testing the remaining candidate 4-cop-win graphs

We present here the results described in section 6 of the article. The code used to generate the base graphs (the first part of the merging algorithm) is available here. The code used to complete the graphs by adding the remaining possible edges (the second part of the merging algorithm) is available here. The breakdown of the cop numbers of these resulting graphs are then computed. We also present the (few) 4-cop-win graphs found.

The results of each step of the algorithm are presented in different colums. Each row corresponds to a different choice of parameters (which are the parameters one needs to choose to execute the code). The order of the rows follows the logical order of computations as described in the article.

Last updated on June 4, 2020.