Suppose a girl, call her Alice is lost from home. Where all her geographical surroundings, including both herself and the position of her house can be modeled as particular vertices in a graph $G$ such that each edge in $G$ corresponds with a road that Alice can walk down as she attempts to find her way home. However Alice is on the phone with her friend Bob, who is trying to give her directions to get back home based on what she tells him of her current surroundings, yet Alice can only see those vertices directly adjacent to her and so Bob must try his best based on her description of where she is to help her navigate back home.
Now my goal is to optimize the graph $G$ to make it as hard as possible for Alice to get home. After rethinking this several times, I can't help but think it involves group theory which seems weird in this particular context as I've not used abstract algebra in related problems of this nature before. Though in any case my train of thought was:
Try to design a graph based on the constraints I was given, such that knowing the neighbors of any vertex gives as little structural information about that vertices positions relative to the graph as a whole, in this way since Alice can only see geographic objects adjacent to her, a graph satisfying this property would ensure Alice conveys as little information about her position as possible to Bob.
However if the graph has a large automorphism group, or is "vertex transitive" then since any vertex can be mapped to any other vertex via a bijective map. This would make the positions (vertices) essentially indistinguishable up to the objects (vertices ) adjacent to Alice's position.
So I'm thinking the more "transitive" I make the graphs automorphism group, the less information Alice will have about her geographic position relative to $G$, which means less info can be given to Bob, which means Alice will likely remain lost longer being unable to give much of a description of her surroundings based on the structure of adjacent vertices.
Though I'm not totally sure I'm interpreting transitive group actions correctly and also the fact that group theory is coming up in an optimization problem seems kind of weird to me, so I think I might be looking at the problem wrong. Is my vague intuition corerct? Or am I (probably) interpreting the relationship between a graphs automorphisms and individual vertices relative distinguish-ability based on their neighbors wrong?
Concepts like vertex transitivity and the automorphism group of a graph seem to address a slightly different problem. Suppose that Alice, from where she's standing, sees the entire structure of $G$, but can't tell the vertices apart in absolute terms: she can only describe them relative to her current position. (I guess we'd still want Alice to need to be sufficiently close to a vertex before she can identify it as her home; otherwise, she could just go there.)
In that case, two vertices are indistinguishable, based on this description, if there's a graph isomorphism that takes one vertex to the other. In particular, if the graph is vertex-transitive, then no two vertices are distinguishable, and Bob can't give Alice any useful advice.
In your case, Alice only has local information about the graph, and there doesn't need to be an isomorphism of the whole graph to make two vertices indistinguishable. The simplest version of the problem is when Alice can count the number of edges/roads out of her current location, but can't see what the destinations look like. (Maybe she'd be able to recognize one of them as home, maybe not; this doesn't really change the problem.)
In this case, two vertices are indistinguishable if they have the same degree. A regular graph is one in which all vertices have the same degree, and so all vertices look alike, and Bob can't help Alice find home.
Finally, we can give Alice just a bit more power. Maybe Alice can look at the adjacent vertices and be able to count their degrees. Or maybe she can see up to $k$ steps away, for some $k$.
I'm not aware of a term for the "hard case" of this problem in general, but one way we could make the problem hard is by looking at regular graphs with a minimum girth. The girth of a graph is the length of the shortest cycle. If Alice is in an $r$-regular graph with girth $2k+1$, then she will always see the same thing when standing at any vertex: "there are $r$ neighboring vertices; each one of them has $r-1$ other neighbors, and each one of those has $r-1$ other neighbors, and so on, and those are all distinct."
Regular graphs with large girth are not hard to come by. In fact, a randomly chosen $r$-regular graph on $n$ vertices will have only a constant number of cycles of lengths $3, 4, \dots, 2k$, as $n$ goes to infinity: this means that only a small fraction of the vertices in the graph look different from the boring uniform description above. With a constant probability (depending on $k$), there will be no such cycles, and all vertices will look the same to Alice.