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.

xxxxxxxxxx

C9 = graphs.CycleGraph(9); C9

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$.

xxxxxxxxxx

D = C9.copy()

D.add_edges([(1,9), (4,10), (7,11)])

D.delete_vertex(0)

Here's $D$:

The automorphism group of $D$ has order 2:

xxxxxxxxxx

D.automorphism_group().order()

and we can determine its orbits:

xxxxxxxxxx

D.automorphism_group(return_group=False, orbits=True)

As an alternative to the last command we can also use

xxxxxxxxxx

D.automorphism_group().orbits()

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

xxxxxxxxxx

E = D.canonical_label()

E.edges(labels=False)

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

xxxxxxxxxx

P = graphs.PetersenGraph()

Q = graphs.CompleteGraph(5).line_graph().complement()

Pc = P.canonical_label(); Qc = Q.canonical_label()

P == Q, Pc == Qc

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$.

xxxxxxxxxx

def vdi(G, i):

    H = G.copy()

    H.delete_vertex(i)

    return (H.canonical_label().graph6_string(), i)

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

xxxxxxxxxx

orbs = D.automorphism_group( return_group=False, orbits=True)

orb_reps = [it[0] for it in orbs]

labels = [vdi(D,i) for i in orb_reps]

labels

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,

xxxxxxxxxx

[(l1[1], l2[1]) for l1 in labels for l2 in labels if (l1[0] == l2[0]) and (l1[1] < l2[1])]

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.)

xxxxxxxxxx

def ls_dict( tuples):

    dc = {}

    for pair in tuples:

        if dc.has_key( pair[0]):

            dc[ pair[0]].append(pair[1])

        else:

            dc[ pair[0]] = [pair[1]]

    return dc

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

xxxxxxxxxx

def get_families( dc, k):

    families = []

    for str, vxs in dc.iteritems():

        if len(vxs) >= k:

            families.append( vxs)

    return families

We apply this to our list labels:

xxxxxxxxxx

get_families( ls_dict( labels), 2)

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.