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?

up vote 1 down vote accepted

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.