<p>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(<span class="math-container">$v$</span>)=out-degree(<span class="math-container">$v$</span>) for all <span class="math-container">$v\in V(G)$</span>). The following are equivalent for a connected graph <span class="math-container">$G$</span> (hence the name Eulerian orientation):</p>
<ol>
<li><span class="math-container">$G$</span> has an Eulerian orientation.</li>
<li>Eery vertex of <span class="math-container">$G$</span> has even degree.</li>
<li><span class="math-container">$G$</span> is Eulerian  (i.e., it has a Euler circuit).</li>
</ol>
<p>Let us focus on <span class="math-container">$2p$</span>-regular graphs <span class="math-container">$G$</span> for the time being. In general, it is computationally hard to list all Eulerian orientations of <span class="math-container">$G$</span> (it is hard even to count all Eulerian orietations; but, sampling algorithm are avaiable).<br />
<strong>Does the listing problem become easier if we demand the Eulerian orientation to satisfy some additional conditions?</strong><br />
Ideally, the conditions should not be too restrctive. Are the following conditions enough to make the listing problem tractable?</p>
<ol>
<li><em>For every vertex <span class="math-container">$x$</span> of <span class="math-container">$G$</span>, the set <span class="math-container">$N^+(x)$</span> of out-neigbours of <span class="math-container">$v$</span> is an indendent set in <span class="math-container">$G$</span>.</em></li>
<li><em>For every pair of vertices <span class="math-container">$x,y$</span> of <span class="math-container">$G$</span> with a common out-neighbour (i.e., <span class="math-container">$N^+(x) \cap N^+(y)\neq \emptyset$</span>), the set <span class="math-container">$N^+(x)\cup N^+(y)$</span> is an independent set in <span class="math-container">$G$</span>.</em></li>
</ol>
<p>Definition<br />
<span class="math-container">$v \text{ is an out-neigbour of } x$</span> if <span class="math-container">$(x,v)$</span> is an arc in the oriented graph.</p>
<p>Disclaimer: This is a follow-up to an <a href="https://cstheory.stackexchange.com/q/48104/47855">earlier question</a>.</p>

CC BY-SA 4.0
2021-04-14T09:35:16.870Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-04-14T10:11:52.660Z
@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.
Cyriac Antony
CC BY-SA 4.0
2021-04-25T19:11:51.863Z
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$?
Neal Young
CC BY-SA 4.0
2021-04-26T05:39:11.190Z
@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).
Cyriac Antony
<graph-theory>
Listing Eulerian orienations with special properties
Cyriac Antony
# Listing Eulerian orienations with special properties

(Asked by: username_0 on 2021-04-14)

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](https://cstheory.stackexchange.com/q/48104/47855).

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: 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$?  
> **username_0**: @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).  

---

## 0 answers

