2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – Stephen Shea
    Commented May 9, 2012 at 11:06
  • 1
    $\begingroup$ I'd go with "conjugate". A quick perusal of Godsil & Royle, Chapters 1-2 didn't yield any alternative terms. $\endgroup$
    – Felix Goldberg
    Commented May 9, 2012 at 11:39

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This matches my experience also. $\endgroup$
    – Brendan McKay
    Commented May 9, 2012 at 12:08
  • $\begingroup$ @Gjergji: thanks, but one thing leaves me a bit unsatisfied: being similar is a rather weak name for two nodes which are essentially indistinguishable. (In category theory two isomorphic objects are essentially the same, not only similar or something like that.) But I don't want to argue, it's just names. And I asked for names. $\endgroup$
    – Hans-Peter Stricker
    Commented May 9, 2012 at 12:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .