Locally isomorphic graphs

Question

If $G=(V,E)$ is a simple undirected graph and $v\in V$ we let the *pointed neighborhood * of $v$ be defined by $$N^*_G(v)=\big\{w\in V:\{v,w\}\in E\big\}\cup\big\{v\big\}.$$

If $G_i=(V_i,E_i)$ are graphs for $i=0,1$ then they are said to be locally isomorphic if there is a bijection $\varphi:V_0\to V_1$ such that for all $v \in V_0$ we have that $N^*_{G_0}(v)$ and $N^*_{G_1}(\varphi(v))$ are isomorphic induced subgraphs of $G_0$ and $G_1$, respectively.

Question. Are there connected locally isomorphic graphs $G_0, G_1$ with $G_0\not\cong G_1$?

Answer 1

Yes, since it is easy to construct triangle-free cubic graphs which are not isomorphic. For example, the Petersen graph and the 5-prism are not isomorphic, but are locally isomorphic, since every pointed neighbourhood in either graph is isomorphic to $K_{1,3}$.

Answer 2

Let $G_0$ be two pentagons ($5$-cycles) connected by an edge: say $V_0 = (\mathbb{Z}/5\mathbb{Z})\times\{0,1\}$ with $(i,p)$ connected to $(i-1,p)$ and $(i+1,p)$ except that $(0,p)$ is also connected to $(0,1-p)$.

Let $G_1$ be a decagon ($10$-cycle) with an extra diameter: say $V_1 = \mathbb{Z}/10\mathbb{Z}$ with $i$ connected to $i-1$ and $i+1$ except that $0$ and $5$ are also connected.

Clearly $G_0$ and $G_1$ are not isomorphic: indeed, by removing the edge connecting $(0,0)$ and $(0,1)$ from $G_0$ we can disconnect it whereas removing any edge from $G_1$ will leave it connected.

However, the bijection $\varphi$ taking $(i,p)$ to $i+5p$ where $i\in\{0,1,2,3,4\}$ and $p\in\{0,1\}$ defines a bijection between $G_0$ and $G_1$ which is a local isomorphism. Indeed, the pointed neighborhoods of a vertex in either graphs are each a $2$-star or a $3$-star (where by “$k$-star” I mean $k$ vertices connected to a central vertex), and the bijection sends the two vertices with a $3$-star pointed neighborhood of one graph to the other (namely $(0,0)$ and $(0,1)$ to $0$ and $5$).