1
$\begingroup$

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

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

0

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.