# Name of vertices in the same orbit

Every now and then I wonder what the official name of the relation $\sim$ between two vertices in a graph $G$ is that are mapped to each other by a graph automorphism, i.e. which are "structurally indistinguishable":

$$x \sim y \quad\text{iff}\quad (\exists g \in \text{Aut}(G))\ x = g(y)$$

I use to call such vertices "conjugate", more cumbersome is "in the same orbit". Rudolf Carnap in Logical Structure of the world uses the term "homotopic" and I dimly remember to have heard the term "homologous".

None of these terms gives many relevant Google results when combined with "graph theory" (but maybe I just searched awkwardly?). But this could also mean, that the concept per se isn't of very big interest in graph theory?

-
You may find an answer in the literature on r-distinguishing labelings (see Symmetry breaking in graphs by Albertson and Collins), or determining sets (see Identifying graph automorphisms using determining sets by Boutin). – Stephen Shea May 9 '12 at 11:06
I'd go with "conjugate". A quick perusal of Godsil & Royle, Chapters 1-2 didn't yield any alternative terms. – Felix Goldberg May 9 '12 at 11:39

In pretty much all texts or papers on graph theory that I've seen two vertices in the same orbit of the automorphism group are called similar. If $G-\lbrace u\rbrace\cong G-\lbrace v\rbrace$ but $u$ and $v$ are not similar, one calls such vertices pseudosimilar. The same terminology is used for edges. You will find that there is a lot of literature on the problem of constructing large sets of pseudosimilar vertices or edges. Unfortunately searching for "similar vertices" is more likely to bring up results that are more devoted to pseudosimilarity, so it's not very efficient for your goal, but it does seem to be the most common terminology in the graph-theory literature.