Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in one direction or both ways.

I'm trying to enumerate all superorientations (isomorphic superorientations count as one) of an undirected graph. Since graph isomorphism problem is NP-intermediate, I never intended to ask digraphs in the enumeration to be pairwise non-isomorphic. But since the list can be exponentially large, I want to make it as compact as possible, or in other words, to make isomorphic graphs as less as possible.

My attempt is given below.


But it yields too many isomorphic graphs. My question is whether we have other ways to work around. Even we cannot make any improvements in general, but how about some special classes of graphs, say symmetric graphs?

Any suggestions or comments are welcome!

  • $\begingroup$ You said "isomorphism is allowed." Do you mean isomorphic superorientations are considered the same, or counted differently? I'm not sure which is meant by "allowed." If the answer is they are counted differently, there are $3^{|E|}$. I suppose if it's not that simple, "allowed" means isomorphic graphs all count as one. $\endgroup$ – Kellen Myers Apr 2 '16 at 22:22
  • $\begingroup$ @KellenMyers Sorry for the confusion caused. When I said allowing isomorphism, I mean all isomorphic superorientations count as one. I will update the description in the post later. $\endgroup$ – Han Xiao Apr 3 '16 at 2:49

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.