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

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?

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.

• Thanks, I see what you mean. Your suggestion is a good point. Just a small detail however, you need to specify $n \ge 2$ for your property to hold on toroidal grids. For $n=1$ it doesn't hold. – goPlayerJuggler Nov 16 '17 at 8:22
• Good catch! I've fixed that. – Misha Lavrov Nov 16 '17 at 15:33