One can represent every group as a directed graph with colored edges (its Cayley graph). Identifying the colors of the edges with specific vertices of the graph (its generators), one ends up with a simple, uncolored digraph. There are interesting questions concerning such digraphs.

I'd like to ask a similar question: Instead of investigating how every group can be represented by a digraph, I'd like to know:

  • How can digraphs be represented by undirected graphs?

  • When are such representations "unique"?

  • How can the undirected graphs be characterized that represent digraphs?

  • How can - eventually - the digraph be reconstructed from its representation as an undirected graph?

One approach is to represent every arrow of the digraph by an extra-vertex and giving it a "direction" - represented by another extra-vertex. Very soon, one stumbles over an example of an undirected graph, that represents two very different digraphs.

(The labels are only for facilitating the reading and comparison of the graphs, they are not essential and are to be ignored.)

enter image description here

enter image description here

But most surely this is only an exception due to the small number of vertices and arrows. I believe, that in general – at least for almost all connected digraphs – the representation will be unique.

Or how can the cases of non-uniqueness be characterized specifically?

Here is another example (to be compared with the first diagram above):

enter image description here

  • $\begingroup$ I don't see how the new vertices are to be put in for a given directed edge, in such a way that one can "go backwards" from the undirected result and recover the direction in the starting directed graph. By the way are the little arrows in your undirected diagrams supposed to be part of the undirected graph, say a distinguished set of vertices? Dropping the little arrows leaves one wondering which way the old edge was directed. $\endgroup$ – coffeemath Jun 13 '13 at 23:55
  • $\begingroup$ I forgot to say, that the digraph can be recovered in principle only up to reversion (of the direction of the arrows). And no, the little arrows are just labels and not part of the graph. $\endgroup$ – Hans-Peter Stricker Jun 14 '13 at 6:44
  • $\begingroup$ Each individual original arrow must have some way to indicate its direction in the undirected new graph, or how can one distinguish it all? What would be the difference in the way 1 --> 2 --> 3 was represented, versus say 1 --> 2 <-- 3, by means of only having single new ends placed emanating from old edges? I still don't see how to do it, since the above two examples I just gave are dissimilar even up to reversion. $\endgroup$ – coffeemath Jun 14 '13 at 8:27
  • $\begingroup$ The idea is, that in the whole undirected graph there will be exactly two vertices representing opposite directions. $\endgroup$ – Hans-Peter Stricker Jun 14 '13 at 10:25
  • 1
    $\begingroup$ I think there is a standard construction in an old paper of the Czech school (probably involving some of Nešetřil, Hell, Pultr, Hedrlín, Vopěnka). IIRC, one creates a rigid gadget (= has no nontrivial automorphisms) that represents a directed edge. The construction allows unambiguous reconstruction. $\endgroup$ – András Salamon Jun 14 '13 at 20:13

Your Answer

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

Browse other questions tagged or ask your own question.