Representation number of a graph



The representation number of a graph is the smallest number k (if it exists) for which the following property holds. Number the nodes from 1 to n, then there is a word over {1,..,n} of length kn in which every number 1,..,n occurs exactly k times, and there is an edge from i to j if and only if after removing all other symbols form the word, the remaining word has no two consecutive equal symbols, so it is either iji...jij, or jij...iji.

For more information on this topic see an overview paper, or even a full book.

The tool

The tool REPRNR computes the representation number of a graph by encoding its definition into a formula, and then calling the SMT solver Z3. It was developed by Hans Zantema after an inspiring invited lecture on this topic by Sergey Kitaev at the DLT conference in Liege in August 2017. For running in Windows a zip file is provided containing For running in Linux a zip file is provided, using the SMT solver yices instead of Z3. It contains

The format

The input consists of of the number n of nodes, followed by summing up all edges. Every edge is indicated by its two node numbers, from 1 to n. To mark the end, the list of edges should end by 0 0. So for the complete graph on three nodes, the input reads:

3
1 2
1 3
2 3
0 0

Some examples are included:
cubegr.txt : the cube
petgr.txt: Peterson's graph
w5gr.txt: the 5-wheel, having no word representation, so the computation should be forced to stop
g4.txt: the graph G4
g5.txt: the graph G5

and without '.txt' extension in Linux. So by running

reprnr < petgr.txt

in the command line mode in Windows, or

./reprnr < petgr

in Linux, it is first established that the Peterson graph is not 2-representable, and then a 3-representing word is computed and shown.

Results

A variation of the tool has been used to show that up to praph isomorphism Moreover, it has been shown that for 7 and 8 nodes, the numbers of graphs that are not 3-representable are 25 and 929, respectively. As exactly the same numbers have shown before to be the numbers of non-representable graphs, this shows that the representation number of a graph on at most 8 nodes cannot be 4 or higher.

For nine nodes it gave the surprising result that apart from G4 there is exactly one more graph on nine nodes with representation number 4.