Graphs in this question are finite, simple and undirected.
For a fixed graph $H$, a graph $G$ is said to be locally-$H$ if for every vertex $v$ of $G$, the neighbourhood of $v$ in $G$ induces $H$ (i.e., $G[N_G(v)]\cong H$).
A function $\psi\colon V(G)\to V(H)$ is a locally bijective homomorphism (LBH) from $G$ to $H$ if for every vertex $v$ of $G$, the restiction of $\psi$ to $N_G(v)$ is a bijection from $N_G(v)$ onto $N_H(\psi(v))$ (observe that such a function $\psi$ is always a homomorphism from $G$ to $H$). An alternate defintion is given in definitions section below.
See [1] for a suvrey on locally constrained graph homomorphisms.
It is known that given a $d$-regular graph $G^*$ with $d\geq 3$, it is NP-complete to test whether an input graph $G$ has an LBH to $G^*$ [1].
I am interested in (the complexity of) the existence of LBH between locally-$H$ graphs. One might expect that both host and target graphs being locally-$H$ would make it easy to test for existence of LBH. But, this is not the case; we proved that the existence problem remains NP-complete when both $G$ and $G^*$ are locally-$2K_2$ (and $G^*$ is the cuboctahedral graph [i.e. the line graph of 3-cube]).
Are there graphs $H$ and $G^*$ such that (i) $G^*$ is locally-$H$, and (ii) given a locally-$H$ graph $G$, one can test in polynomial time whether $G$ admits an LBH to $G^*$?
(It seems reasonable to expect an yes answer to this question).
Context
In [2], we defined a family of graphs $\{G_{2p}\colon p\in\mathbb{N}, p\geq 2\}$ such that $G_{2p}$ is a vertex-transitive $2p$-regular graph (in fact, $G_{2p}$ is arc-transitive). The graph $G_4$ is the cuboctahedral graph. More importantly here, $G_{2p}$ is locally-$pK_2$. In general, given a graph $G$, it is NP-complete to test whether $G$ has an LBH to $G_{2p}$ by [1] (since $G_{2p}$ is regular). We are interested in the complexity when $G$ is locally-$pK_2$ as well. We proved that given a locally-$2K_2$ graph $G$, it is NP-complete to test whether $G$ has an LBH to $G_4$ (unpublished). I personally suspect that for all $p\geq 2$, given a locally-$pK_2$ graph $G$, it is NP-complete to test whether $G$ has an LBH to $G_{2p}$. In the mean-time, we would like to gather evidence that both host and target graphs being locally-$H$ does indeed help at least for some choices of $H$.
Definitions
A homomorphism from a graph $G$ to a graph $H$ is a fuction $\psi\colon V(G)\to V(H)$ such that $\psi(u)\psi(v)\in E(H)$ whenever $uv\in E(G)$. If $\psi$ is a homomorphism from a graph $G$ to a graph $H$ and $\psi(v)=w$, we say that $v$ is a copy of $w$ in $G$.
A function $\psi\colon V(G)\to V(H)$ is a locally bijective homomorphism from $G$ to $H$ if for every vertex $v$ of $G$, the restiction of $\psi$ to $N_G(v)$ is a bijection from $N_G(v)$ onto $N_H(\psi(v))$ (such a function $\psi$ is always a homomorphism from $G$ to $H$).
In other words, a homomorphism $\psi$ from $G$ to $H$ is locally bijective if for each vertex $w$ of $H$ and each neighbour $x$ of $w$ in $H$, each copy of $w$ in $G$ has exactly one copy of $x$ in $G$ as its neighbour.
In the figure above, vertices in $H$ are labelled distinct and are drawn by distinct shapes, whereas each copy of $w$ in $G$ has the same label and shape as $w$.
A graph $G(V,E)$ is arc-transitive if for every $(v,w,x,y)\in V^4$ with $vw\in E(G)$ and $xy\in E(G)$, there exists an automorphism $\psi$ of $G$ such $\psi(v)=x$ and $\psi(w)=y$. By definition, an arc-transitive graph is both vertex-transitive and edge-transitive.
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] Shalu, M A; Antony, Cyriac, Star colouring of bounded degree graphs and regular graphs, Discrete Mathematics (2022), doi: 10.1016/j.disc.2022.112850.
