Local homogeneity properties satisfied by toroidal grids - terminology and results in the literature

Question

The toroidal grids $C_p\square C_q$ ($C_p\square C_q$ is the Cartesian product of the cyclic graphs of order $p$ and $q$) are graphs $G$ satisfying the local homogeneity property $P(G)$ defined by: given any two points, there exists an isomorphism between the closed neighbourhoods of these points that can be extended to an automorphism of the whole graph $G$. (Why? simply take the translation that maps the first point to the second.)

A generalisation: the local homogeneity property $Q_n(G)$ where given any two points $x$ and $y$ in the graph $G$, there exists an automorphism of G which induces an isomorphism from the subgraph of points of distance $\le n$ from $x$ to the the subgraph of points of distance $\le n$ from $y$. Again, toroidal grids satisfy this property.

My questions:

1. is there a commonly accepted term for the property $P$ and for the class of graphs with this property?

2. is there a commonly accepted term for the property $Q_n$ and for the class of graphs with this property?

3. do any results exist along the lines of classifying finite graphs with these properties?

Answer 1

As stated, both of your properties are equivalent to the property of being a vertex-transitive graph.

In a vertex transitive graph, given any two vertices $v$ and $w$, there is a graph automorphism $\phi$ that takes $v$ to $w$. In particular:

• There exists an isomorphism between $N(v) \cup \{v\}$ and $N(w) \cup \{w\}$ (the restriction of $\phi$ to $N(v) \cup \{v\}$) that extends to a graph automorphism ($\phi$ itself).
• There exists an isomorphism between $\{x \in V : d(v,x) \le n\}$ and $\{x \in V : d(w,x) \le n\}$ (the restriction of $\phi$ to the first of these sets) that extends to a graph automorphism ($\phi$ itself).

However, for $n \ge 2$, the toroidal grids have a stronger property that might be what you're trying to get at: given any two vertices $v$ and $w$, any isomorphism between $\{x \in V: d(v,x) \le n\}$ and $\{x \in V : d(w,x) \le n\}$ extends to an automorphism of $G$.

Such graphs have not been studied, as far as I know; if I had to make up a name for them, I'd call the $n=1$ case "neighborhood-transitive graphs" and the general case "$n$-neighborhood-transitive graphs".

All Cayley graphs have this property for all $n$. But these are not all the examples: the complete bipartite graph $K_{n,n}$ is another example, and it is not in general a Cayley graph.