# 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
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.