Section2.1Pseudosimilar Vertices

Vertices $u$ and $v$ in a graph $X$ are similar if there is an automorphism of $X$ that maps $u$ to $v$. If $u$ and $v$ are similar, then the vertex-deleted subgraphs $X\diff u$ and $X\diff v$ are isomorphic. If $X\diff u$ and $X\diff v$ are isomorphic but $u$ and $v$ are not similar, we say that they are pseudosimilar. It is not obvious that pairs of pseudosimilar vertices exist, but we will see that they do.

The vertex set of $C9$ is $\{0,\ldots,8\}$. We want to add three new vertices to $C9$, adjacent to $1$, $4$ and $7$ in turn and delete the vertex $0$.

Here's $D$:

The automorphism group of $D$ has order 2:

and we can determine its orbits:

As an alternative to the last command we can also use

I claim $D$ has a pair of pseudosimilar vertices. In this case we could find them by inspecting our drawing of $D$, but we work through a general approach. The idea is to find a canonical label for each of the 11 vertex-deleted subgraphs of $D$. The sage command

returns a canonized form of $D$. So graphs $G$ and $H$ are isomorphic if and only if their canonized forms are equal. For example

The only problem left is that the return value of canonical_label() is not hashable. We can circumvent this as follows.

The following procedure constructs a hashable canonical label for $G\diff i$, given $G$ and $i$.

We can now construct our list of pairs of the form (string, vertex):

and on inspecting the output, we see that $D\diff 3\cong D\diff 6$, which we can also ask Sage to do for us instead via a one-line list comprehension,

As an exercise, construct a graph on 8 vertices with a pair of pseudosimilar vertices.

Now we describe how to get a list of the sets of vertices such that all vertices in the same set have the same vertex-deleted subgraphs. First we need to convert our list of pairs to a dictionary keyed on the first term of the pair; the value of a key will be all second terms with the same first term. (The keys for a dictionary must be hashable, so this is why we needed the graph6 strings.)

Now if dc is a dictionary whose values are lists, we compute a list consisting of those values whose length is at least $k$:

We apply this to our list labels:

We see again that 3 and 6 form a pseudosimilar pair of vertices.

For further reading on pseudosimilar vertices, you will have to dig out papers on the topic. I suspect that few of these are on the web, since they predate $\mathrm{\LaTeX}$. Fortunately we still have libraries. Note that pseudosimilar sets of size greater than two are possible.