# Properties of half-way locally bijective homomorphisms between Eulerian orientations

## 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.

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 [1] or the wikipedia page.

(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, Comput. Sci. Rev. 2, No. 2, 97-111 (2008). ZBL1302.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).

• 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. Dec 26, 2021 at 7:43
• 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". Dec 30, 2021 at 10:57
• To clarify, both graphs $G$ and $H$ in the question are finite and simple (no multiple edges or loops). Jan 2 at 2:47