0
$\begingroup$

An orientation of a simple undirected graph is said to be Eulerian if every vertex has the same number of in-coming edges and out-going edges (i.e., in-degree($v$)=out-degree($v$) for all $v\in V(G)$). The following are equivalent for a connected graph $G$ (hence the name Eulerian orientation):

  1. $G$ has an Eulerian orientation.
  2. Eery vertex of $G$ has even degree.
  3. $G$ is Eulerian (i.e., it has a Euler circuit).

Let us focus on $2p$-regular graphs $G$ for the time being. In general, it is computationally hard to list all Eulerian orientations of $G$ (it is hard even to count all Eulerian orietations; but, sampling algorithm are avaiable).
Does the listing problem become easier if we demand the Eulerian orientation to satisfy some additional conditions?
Ideally, the conditions should not be too restrctive. Are the following conditions enough to make the listing problem tractable?

  1. For every vertex $x$ of $G$, the set $N^+(x)$ of out-neigbours of $v$ is an indendent set in $G$.
  2. For every pair of vertices $x,y$ of $G$ with a common out-neighbour (i.e., $N^+(x) \cap N^+(y)\neq \emptyset$), the set $N^+(x)\cup N^+(y)$ is an independent set in $G$.

Definition
$v \text{ is an out-neigbour of } x$ if $(x,v)$ is an arc in the oriented graph.

Disclaimer: This is a follow-up to an earlier question.

$\endgroup$
4
  • $\begingroup$ As far I can see, the primary problem is that the number of Eulerian orientations can be exponential, which means that listing them trivially requires exponential time. Do you expect the conditions to imply that the graph has only a small (polynomial?) number of Eulerian orientations? If not, what do you mean by “easier”? Also, note that if the graph is bipartite, your two conditions are satisfied by all Eulerian orientations, so I doubt they can make a significant difference. $\endgroup$ – Emil Jeřábek Apr 14 at 9:35
  • $\begingroup$ @EmilJeřábek Ah, yes. The bipartite case itself spoils the possibilities. And yes, I was looking for conditions that make the number of Eulerian orientations small. $\endgroup$ – Cyriac Antony Apr 14 at 10:11
  • $\begingroup$ It seems unlikely that any such restrictions can make the number of Eulerian orientations sub-exponential. Given any $2p$-regular graph $G$ with at least two valid orientations, construct a graph $G_N$ by making $N$ independent copies of $G$. Then won't the number of valid orientations of $G_N$ be at least $2^N$? $\endgroup$ – Neal Young Apr 25 at 19:11
  • $\begingroup$ @NealYoung The special case you mentioned can be avoided by demanding connectedness. But, I am afraid your main point is valid (unless the restrictions imposed are very strong). $\endgroup$ – Cyriac Antony Apr 26 at 5:39

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.