<h2>Short Version</h2>
<p>Let <span class="math-container">$G$</span> and <span class="math-container">$H$</span> be two Eulerian graphs and let <span class="math-container">$\overrightarrow{G}$</span> and  <span class="math-container">$\overrightarrow{H}$</span> be Eulerian orientations of those graphs. Let <span class="math-container">$f$</span> be a homomorphism from <span class="math-container">$G$</span> to <span class="math-container">$H$</span>.<br />
(Definition) <span class="math-container">$f$</span> is a <strong>locally bijective homomorphism</strong> from <span class="math-container">$G$</span> to <span class="math-container">$H$</span> if<br />
(a) each vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span> is said to a copy of <span class="math-container">$f(v)$</span>, and<br />
(b) the following hold for each vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span>:<br />
<span class="math-container">$\phantom{X}$</span>(b.1) <span class="math-container">$\deg_G(v)=\deg_H(f(v))$</span>, and<br />
<span class="math-container">$\phantom{X}$</span>(b.2) <strong>neighbours</strong> of <span class="math-container">$v$</span> in <span class="math-container">$G$</span> are copies of <strong>neighbours</strong> of <span class="math-container">$f(v)$</span> in <span class="math-container">$H$</span>.</p>
<p>(Property) If <span class="math-container">$f$</span> is a locally bijective homomorphism from <span class="math-container">$G$</span> to <span class="math-container">$H$</span>, then <span class="math-container">$|f^{-1}(u)|=|f^{-1}(v)|$</span>  for all <span class="math-container">$u,v\in V(H)$</span> [1].</p>
<p>(Definition) We say that <span class="math-container">$f$</span> is a <strong>half-way locally bijective homomorphism</strong> from <span class="math-container">$\overrightarrow{G}$</span> to  <span class="math-container">$\overrightarrow{H}$</span> if the above conditions are satisfied with &quot;neighbours&quot; in (b.2) replaced by &quot;out-neighbours&quot; [and <span class="math-container">$G$</span> and <span class="math-container">$H$</span> in (b.2) replaced by <span class="math-container">$\overrightarrow{G}$</span> and  <span class="math-container">$\overrightarrow{H}$</span>].</p>
<p>We have example graphs <span class="math-container">$\overrightarrow{H}$</span> such that<br />
<span class="math-container">$\overrightarrow{G}$</span> has a half-way locally bijective homomorphism to <span class="math-container">$\overrightarrow{H}$</span> <span class="math-container">$\implies$</span> <span class="math-container">$|f^{-1}(u)|=|f^{-1}(v)|$</span> for all <span class="math-container">$u,v\in V(H)$</span>.</p>
<p><strong>What conditions on <span class="math-container">$\overrightarrow{H}$</span> (or <span class="math-container">$H$</span>) are sufficient to ensure the above property?</strong></p>
<h2>Long Version</h2>
<p>An <em>orientation</em> of a (undirected) graph <span class="math-container">$G$</span> is a directed graph obtained from <span class="math-container">$G$</span> by assigning some direction to each edge of <span class="math-container">$G$</span>. An orientation <span class="math-container">$\overrightarrow{G}$</span> of <span class="math-container">$G$</span> is said to be an <em>Eulerian orientation</em> if for each vertex <span class="math-container">$v$</span> of <span class="math-container">$\overrightarrow{G}$</span>, the number of in-neighbours of <span class="math-container">$v$</span> equals the number of out-neighbours of <span class="math-container">$v$</span>.</p>
<p>Let <span class="math-container">$G$</span> and <span class="math-container">$H$</span> be two Eulerian graphs (i.e. connected even-degree graphs) and let <span class="math-container">$\overrightarrow{G}$</span> and  <span class="math-container">$\overrightarrow{H}$</span> be Eulerian orientations of those graphs.
Let <span class="math-container">$f$</span> be a homomorphism from <span class="math-container">$G$</span> to <span class="math-container">$H$</span> [i.e., <span class="math-container">$f\colon V(G)\to V(H)$</span> satisfy <span class="math-container">$uv\in E(G)\implies f(u)f(v)\in E(H)$</span>].</p>
<p>(Definition) <span class="math-container">$f$</span> is a <strong>locally bijective homomorphism</strong> from <span class="math-container">$G$</span> to <span class="math-container">$H$</span> (also called a covering map) if<br />
(a) each vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span> is said to a copy of <span class="math-container">$f(v)$</span>, and<br />
(b) the following hold for each vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span>:<br />
<span class="math-container">$\phantom{X}$</span>(b.1) <span class="math-container">$\deg_G(v)=\deg_H(f(v))$</span>, and<br />
<span class="math-container">$\phantom{X}$</span>(b.2) <strong>neighbours</strong> of <span class="math-container">$v$</span> in <span class="math-container">$G$</span> are copies of <strong>neighbours</strong> of <span class="math-container">$f(v)$</span> in <span class="math-container">$H$</span>.</p>
<p>(Example) Vertices in <span class="math-container">$H$</span> are drawn as distinct shapes, and all copies of a vertex are drawn by the same shape.<br />
<a href="https://i.sstatic.net/iTaD0.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/iTaD0.png" alt="enter image description here" /></a><br />
Image credit: Fiala and Kratochvíl [1]</p>
<p>(Property)<br />
If <span class="math-container">$f$</span> is a locally bijective homomorphism from <span class="math-container">$G$</span> to <span class="math-container">$H$</span>, then <span class="math-container">$|f^{-1}(u)|=|f^{-1}(v)|$</span> for every pair of vertices <span class="math-container">$u,v$</span> from <span class="math-container">$H$</span> (<span class="math-container">$\because$</span> for every edge <span class="math-container">$xy$</span> of <span class="math-container">$H$</span>, each copy of <span class="math-container">$x$</span> has exactly one copy of <span class="math-container">$y$</span> as nbr, and each copy of <span class="math-container">$y$</span> has exactly one copy of <span class="math-container">$x$</span> as nbr) [1].</p>
<p>For more details on locally bijective homomorphism, see <a href="http://dx.doi.org/10.1016/j.cosrev.2008.06.001" rel="nofollow noreferrer">this survey</a> [1] or <a href="https://en.wikipedia.org/wiki/Covering_graph" rel="nofollow noreferrer">the wikipedia page</a>.</p>
<p>(Definition) <span class="math-container">$f$</span> is a <strong>half-way locally bijective homomorphism</strong> from <span class="math-container">$\overrightarrow{G}$</span> to <span class="math-container">$\overrightarrow{H}$</span> if<br />
(a) each vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span> is said to a copy of <span class="math-container">$f(v)$</span>, and<br />
(b) the following hold for each vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span>:<br />
<span class="math-container">$\phantom{X}$</span>(b.1) <span class="math-container">$\deg_G(v)=\deg_H(f(v))$</span>, and<br />
<span class="math-container">$\phantom{X}$</span>(b.2) <strong>out-neighbours</strong> of <span class="math-container">$v$</span> in <span class="math-container">$\overrightarrow{G}$</span> are copies of <strong>out-neighbours</strong> of <span class="math-container">$f(v)$</span> in <span class="math-container">$\overrightarrow{H}$</span>.</p>
<p>We have example graphs <span class="math-container">$\overrightarrow{H}$</span> such that<br />
<span class="math-container">$\overrightarrow{G}$</span> has a half-way locally bijective homomorphism to <span class="math-container">$\overrightarrow{H}$</span> <span class="math-container">$\implies$</span> <span class="math-container">$|f^{-1}(u)|=|f^{-1}(v)|$</span> for all <span class="math-container">$u,v\in V(H)$</span>.<br />
One such example as <span class="math-container">$\overrightarrow{H}$</span> is a plane drawing of cuboctohedron graph such that all face boundaries are oriented cyclically (some of them c.w. and the rest c.c.w.).</p>
<p>In general, we can say this:
If <span class="math-container">$\overrightarrow{G}$</span> has a locally bijective homomorphism to <span class="math-container">$\overrightarrow{H}$</span> and <span class="math-container">$v$</span> is a vertex in <span class="math-container">$\overrightarrow{H}$</span> with in-neighbours <span class="math-container">$u_1,u_2,\dots,u_p$</span>, then <span class="math-container">$\sum_{i=1}^{p}|f^{-1}(u_i)|=p|f^{-1}(v)|$</span>.</p>
<p><strong>What conditions on <span class="math-container">$\overrightarrow{H}$</span> (or <span class="math-container">$H$</span>) are sufficient to ensure that <span class="math-container">$\overrightarrow{G}$</span> has a half-way locally bijective homomorphism to <span class="math-container">$\overrightarrow{H}$</span> <span class="math-container">$\implies$</span> <span class="math-container">$|f^{-1}(u)|=|f^{-1}(v)|$</span> for all <span class="math-container">$u,v\in V(H)$</span>?</strong></p>
<h2>Extra-Question</h2>
<p>For every regular graph <span class="math-container">$H$</span> of maximum degree <span class="math-container">$d\geq 3$</span>, it is NP-complete to test whether an input graph has a locally bijective homomorphism to <span class="math-container">$H$</span> [2].</p>
<p><em>Is the same true about half-way locally bijective homomorphisms?</em><br />
i.e., for a fixed Eulerian orientation <span class="math-container">$\overrightarrow{H}$</span> of a fixed graph <span class="math-container">$H$</span>, is it NP-complete to check whether an input graph <span class="math-container">$G$</span> admits an Eulerian orientation <span class="math-container">$\overrightarrow{G}$</span> such that <span class="math-container">$\overrightarrow{G}$</span> has a half-way locally bijective homomorphism to <span class="math-container">$\overrightarrow{H}$</span>?</p>
<h2>References</h2>
<p>[1] <em>Fiala, Jiří; Kratochvíl, Jan</em>, <a href="http://dx.doi.org/10.1016/j.cosrev.2008.06.001" rel="nofollow noreferrer"><strong>Locally constrained graph homomorphisms – structure, complexity, and applications</strong></a>, Comput. Sci. Rev. 2, No. 2, 97-111 (2008). <a href="https://zbmath.org/?q=an:1302.05122" rel="nofollow noreferrer">ZBL1302.05122</a>.</p>
<p>[2] Fiala, J. (2000). Note on the computational complexity of covering regular graphs. In 9th Annual Conference of Doctoral Students, WDS’00 (pp. 89-90).</p>

CC BY-SA 4.0
2021-12-26T07:43:44.917Z
By the way, half-way locally bijective homomorphism is a notion we introduced. If you are aware of this notion already in the literature, please let me know. Thanks.
Cyriac Antony
CC BY-SA 4.0
2021-12-30T10:57:08.030Z
It came to my attention that for locally injective homomorphisms, this notion is studied in the literature under the name *homomorphism injective on in-neighbourhoods*, e.g. in MacGillivray and Swarts, "The complexity of locally injective homomorphisms".
Cyriac Antony
CC BY-SA 4.0
2022-01-02T02:47:32.980Z
To clarify, both graphs $G$ and $H$ in the question are finite and simple (no multiple edges or loops).
Cyriac Antony
<graph-theory><homomorphism>
Properties of half-way locally bijective homomorphisms between Eulerian orientations
Cyriac Antony
# Properties of half-way locally bijective homomorphisms between Eulerian orientations

(Asked by: username_0 on 2021-12-26)

## Short Version

Let $G$ and $H$ be two Eulerian graphs and let $\overrightarrow{G}$ and $\overrightarrow{H}$ be Eulerian orientations of those graphs. Let $f$ be a homomorphism from $G$ to $H$.  
(Definition) $f$ is a **locally bijective homomorphism** from $G$ to $H$ if  
(a) each vertex $v$ of $G$ is said to a copy of $f(v)$, and  
(b) the following hold for each vertex $v$ of $G$:  
$\phantom{X}$(b.1) $\deg\_G(v)=\deg\_H(f(v))$, and  
$\phantom{X}$(b.2) **neighbours** of $v$ in $G$ are copies of **neighbours** of $f(v)$ in $H$.

(Property) If $f$ is a locally bijective homomorphism from $G$ to $H$, then $|f^{-1}(u)|=|f^{-1}(v)|$ for all $u,v\in V(H)$ [1].

(Definition) We say that $f$ is a **half-way locally bijective homomorphism** from $\overrightarrow{G}$ to $\overrightarrow{H}$ if the above conditions are satisfied with "neighbours" in (b.2) replaced by "out-neighbours" [and $G$ and $H$ in (b.2) replaced by $\overrightarrow{G}$ and $\overrightarrow{H}$].

We have example graphs $\overrightarrow{H}$ such that  
$\overrightarrow{G}$ has a half-way locally bijective homomorphism to $\overrightarrow{H}$ $\implies$ $|f^{-1}(u)|=|f^{-1}(v)|$ for all $u,v\in V(H)$.

**What conditions on $\overrightarrow{H}$ (or $H$) are sufficient to ensure the above property?**

## Long Version

An *orientation* of a (undirected) graph $G$ is a directed graph obtained from $G$ by assigning some direction to each edge of $G$. An orientation $\overrightarrow{G}$ of $G$ is said to be an *Eulerian orientation* if for each vertex $v$ of $\overrightarrow{G}$, the number of in-neighbours of $v$ equals the number of out-neighbours of $v$.

Let $G$ and $H$ be two Eulerian graphs (i.e. connected even-degree graphs) and let $\overrightarrow{G}$ and $\overrightarrow{H}$ be Eulerian orientations of those graphs.
Let $f$ be a homomorphism from $G$ to $H$ [i.e., $f\colon V(G)\to V(H)$ satisfy $uv\in E(G)\implies f(u)f(v)\in E(H)$].

(Definition) $f$ is a **locally bijective homomorphism** from $G$ to $H$ (also called a covering map) if  
(a) each vertex $v$ of $G$ is said to a copy of $f(v)$, and  
(b) the following hold for each vertex $v$ of $G$:  
$\phantom{X}$(b.1) $\deg\_G(v)=\deg\_H(f(v))$, and  
$\phantom{X}$(b.2) **neighbours** of $v$ in $G$ are copies of **neighbours** of $f(v)$ in $H$.

(Example) Vertices in $H$ are drawn as distinct shapes, and all copies of a vertex are drawn by the same shape.  
[![enter image description here](https://i.sstatic.net/iTaD0.png)](https://i.sstatic.net/iTaD0.png)  
Image credit: Fiala and Kratochvíl [1]

(Property)  
If $f$ is a locally bijective homomorphism from $G$ to $H$, then $|f^{-1}(u)|=|f^{-1}(v)|$ for every pair of vertices $u,v$ from $H$ ($\because$ for every edge $xy$ of $H$, each copy of $x$ has exactly one copy of $y$ as nbr, and each copy of $y$ has exactly one copy of $x$ as nbr) [1].

For more details on locally bijective homomorphism, see [this survey](http://dx.doi.org/10.1016/j.cosrev.2008.06.001) [1] or [the wikipedia page](https://en.wikipedia.org/wiki/Covering_graph).

(Definition) $f$ is a **half-way locally bijective homomorphism** from $\overrightarrow{G}$ to $\overrightarrow{H}$ if  
(a) each vertex $v$ of $G$ is said to a copy of $f(v)$, and  
(b) the following hold for each vertex $v$ of $G$:  
$\phantom{X}$(b.1) $\deg\_G(v)=\deg\_H(f(v))$, and  
$\phantom{X}$(b.2) **out-neighbours** of $v$ in $\overrightarrow{G}$ are copies of **out-neighbours** of $f(v)$ in $\overrightarrow{H}$.

We have example graphs $\overrightarrow{H}$ such that  
$\overrightarrow{G}$ has a half-way locally bijective homomorphism to $\overrightarrow{H}$ $\implies$ $|f^{-1}(u)|=|f^{-1}(v)|$ for all $u,v\in V(H)$.  
One such example as $\overrightarrow{H}$ is a plane drawing of cuboctohedron graph such that all face boundaries are oriented cyclically (some of them c.w. and the rest c.c.w.).

In general, we can say this:
If $\overrightarrow{G}$ has a locally bijective homomorphism to $\overrightarrow{H}$ and $v$ is a vertex in $\overrightarrow{H}$ with in-neighbours $u\_1,u\_2,\dots,u\_p$, then $\sum\_{i=1}^{p}|f^{-1}(u\_i)|=p|f^{-1}(v)|$.

**What conditions on $\overrightarrow{H}$ (or $H$) are sufficient to ensure that $\overrightarrow{G}$ has a half-way locally bijective homomorphism to $\overrightarrow{H}$ $\implies$ $|f^{-1}(u)|=|f^{-1}(v)|$ for all $u,v\in V(H)$?**

## Extra-Question

For every regular graph $H$ of maximum degree $d\geq 3$, it is NP-complete to test whether an input graph has a locally bijective homomorphism to $H$ [2].

*Is the same true about half-way locally bijective homomorphisms?*  
i.e., for a fixed Eulerian orientation $\overrightarrow{H}$ of a fixed graph $H$, is it NP-complete to check whether an input graph $G$ admits an Eulerian orientation $\overrightarrow{G}$ such that $\overrightarrow{G}$ has a half-way locally bijective homomorphism to $\overrightarrow{H}$?

## References

[1] *Fiala, Jiří; Kratochvíl, Jan*, [**Locally constrained graph homomorphisms – structure, complexity, and applications**](http://dx.doi.org/10.1016/j.cosrev.2008.06.001), Comput. Sci. Rev. 2, No. 2, 97-111 (2008). [ZBL1302.05122](https://zbmath.org/?q=an:1302.05122).

[2] Fiala, J. (2000). Note on the computational complexity of covering regular graphs. In 9th Annual Conference of Doctoral Students, WDS’00 (pp. 89-90).

**Tags:** graph-theory, homomorphism

> **Comments:**
> **username_0**: By the way, half-way locally bijective homomorphism is a notion we introduced. If you are aware of this notion already in the literature, please let me know. Thanks.  
> **username_0**: It came to my attention that for locally injective homomorphisms, this notion is studied in the literature under the name *homomorphism injective on in-neighbourhoods*, e.g. in MacGillivray and Swarts, "The complexity of locally injective homomorphisms".  
> **username_0**: To clarify, both graphs $G$ and $H$ in the question are finite and simple (no multiple edges or loops).  

---

## 0 answers

