# Locally bijective homomorphism between locally-H graphs

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.