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.
The notion semi-transitive has been proven to be equivalent to having a finite representation number; for details we refer to the above mentioned book. We also provide a tool SEMITR checking for being semi-transitive, and if so, presenting a corresponing orientation. Again the implementation builds a formula reflecting the definition, and then calls the SMT solver. For running in Windows a zip file is provided containing

the executable tool REPRNR to be run in Windows in command line;
the executable tool SEMITR to be run in Windows in command line;
some auxiliary files like the SMT solver Z3;
some example graphs.

For running in Linux a zip file is provided, using the SMT solver yices instead of Z3. It contains

the executable tool REPRNR to be run in Linux in command line;
the executable tool SEMITR to be run in Linux in command line;
some auxiliary files like the SMT solver yices;
some example graphs.

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

the prism on the triangle is the only graph on 6 nodes with representation number 3;
there are exactly 39 connected graphs on 7 nodes with representation number 3;
there are exactly 1852 connected graphs on 8 nodes with representation number 3.

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.