3
$\begingroup$

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 ;)

$\endgroup$
  • 1
    $\begingroup$ In think to find the smallest circle you have to look for a short way to express $56$ as the sum of your numbers $1,2,3,4$ or $1,5,9,13$ respectively. It needs 14 terms in the first case: $4+4+\cdots+4$. It needs 8 in the latter one: $13+13+13+13+1+1+1+1$. This, of course, is no proof. $\endgroup$ – M. Winter May 11 '17 at 7:02
  • $\begingroup$ You still got some multiple short paths to the same vertex, e.g. $5+5=9+1$, $13+1=9+5$ and $9+9=13+5$. I think you cannot do much better. What multiple path lengths are acceptable? $\endgroup$ – M. Winter May 11 '17 at 10:37
  • 1
    $\begingroup$ If you consider length three as short too, then there are still $1+3+3=7$ and $7+3+3=13$ ;). But there is no way to avoid this for $56$ vertices, because every vertex is left by four edges and after three vertices with no double path this would give $4^3=64$ vertices, which is too much for your graph. So I think this is close to best possible. $\endgroup$ – M. Winter May 11 '17 at 12:12
  • 1
    $\begingroup$ I didn't think a lot about multiple paths, good point. I'll fiddle a bit with other increments to reduce it, so far I'm quite happy with +1+3+7+15 : girth of 6 (15+15+15+7+3+1, still ok), no double short path of length 2, and no pair/triplets of same vertex from another one : with+1+5+9+13 you could go to 1,5,9,13 from vertex 0, and to 5, 9, 13, 17 from vertex 4, having twice the 5, 9, 13 ! To avoid this, I found that there must be unique differences between my 4 step increments. With +1+3+7+15 I have differences of 2, 4, 8, 6, 12 & 14, so it's perfect. $\endgroup$ – Keelhaul May 11 '17 at 12:25
3
$\begingroup$

You are looking for a connected vertex-transitive 8-regular directed graph on 56 vertices with high girth. I will explicitly construct such a graph:

  • The vertices receive labels 0 to 55.
  • There is a directed edge from vertex $a$ to vertices $a+1,a+2,a+3,a+4$, where all indices are modulo 56.

This is an example of a circulant graph. Choosing the smallest steps possible – 1, 2, 3 and 4 vertices forward – ensures that the girth is as high as possible: in our construction it is 14.

From any vertex, four vertices are reachable in one step, seven in two steps and ten in three steps.

$\endgroup$
  • $\begingroup$ Great (and simple) answer ! Plus, thanks for the edit. $\endgroup$ – Keelhaul May 10 '17 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.