First of all, my apologies for the naive phrasing of the problem I could make: English is not my first language and graph theory is not my specialty, so I may not use the correct vocabulary for the problem I describe. That being said…
I have 56 nodes. Each node must point to 4 other nodes and be pointed at from 4 other nodes, avoiding if possible reciprocal pointings (i.e. A and B do not point to each other). I also want each node to be accessible from any other node through this succession of directed links (so, only one graph).
What is the most "symmetrical" way to link all 56 nodes, so there is no difference if we look at the graph from node A or X? Is it even possible?
I guess that the longer the routes from one node to itself, the better ($A\to B\to C\to A$ is not so good, avoid if possible). My other guess is that, if symmetry is indeed possible, we will have something like "for every node, you can go to 4 nodes on one step, $X$ (16?) other nodes on 2 steps, $Y$ (not 64 obviously) other nodes on 3 steps…" until every node is at a maximal distance of every other. Hoping I'm clear enough…
In fact, maybe the background of this could help: I'm creating a tabletop game based on 56 tiles, each defined by a unique code, and having 4 other codes leading to the corresponding other tiles. Think dominos, only that each domino can only lead to 4 other dominos, with no reciprocity.
No tile should stand up from the others, hence the symmetrical aspect of the request. For example, we should avoid having tile A at a maximal distance of 3 of every other tile, while tile B could be 5 links away of tile C.
Thank you for your help, and don't hesitate to ask for details if this isn't clear enough.
EDIT since Parcly Taxel answer :
A flaw I see in the +1+2+3+4 solution is that from a vertex to the next, you can easily find most of the same related vertices (from vertices 0 to 1 you can go to the same vertices 2, 3 & 4), which could lead to unexpected game behaviours.
I tried +1+5+9+13 for the first vertices and it seems to work better on that point (with a girth of 8, still acceptable). I will check this more thoroughly to confirm though.
Is there a way to quickly compute the girth and "reachabilities" from a given set of steps ?
EDIT since M. Winter comments :
So, the simplest solution seems to be that of Parcly Taxel :
The vertices receive labels 0 to 55.
There is a directed edge from vertex aa to vertices a+1,a+2,a+3,a+4a+1,a+2,a+3,a+4, where all indices are modulo 56.
However, we saw in the previous edit that the steps +1+2+3+4 are not really great since it tends to repeat some triplets of vertices. In fact, I found that there must be unique differences between the 4 step increments. For example :
- With +1+3+7+15 I have differences of 2, 4, 8, 6, 12 & 14, so it's perfect : no vertex will lead to the same pair or triplets of vertices.
- With +1+3+7+13 however, we have the same diffferences : 7-1 = 13-7 = 6. Hence, from vertex 0 we can go to (1, 3, 7, 13), and from vertex 6 to (7, 9, 13, 19) : both can lead to 7 & 13.
Another issue is the multiple path of length 2. Considering +1+3+7+13, wee se that there is 3 paths of length 2 from a same vertex to another, as for example : $0 \to 7 \to 14$ , $0 \to 1 \to 14$ and $0 \to 13 \to 14$. Here again, if all the differences between the steps are unique, we should not have this kind of behaviour.
The bonus question is : what is the best quadruplet of steps wich ensures this "differences uniqueness", while maximizing the girth ? So far I have +1+3+7+15, with a girth of 6 (56 = 15+15+15+7+3+1), but I'm not done searching ;)