# Generating non-isomorphic graph by adding two edges to a fixed graph

I am given a graph $G$ a fixed vertex $v \in V(G)$ and sets $S_1,S_2 \subseteq V(G).$ The problem I am currently studying requires to answer the following question

Compute all non-isomorphic graphs obtained by adding an edge from $v$ to a vertex in $S_1$ and an edge from $v$ to a vertex in $S_2.$

If I am only looking for non-isomorphic ways to add a single edge with one endpoint in $v$ and one endpoint in $S_1$ then it appears to be easy: Compute the orbits $O$ of the stabilizer $\rm{Aut}(G)_v$ and then consider only edges from $v$ to the "right" representatives of $O.$

I assume the same can be done when adding two edges - one just need consider the orbitals on $\rm{Aut}(G)_v.$ But I would like to make sure this is the best way.

• Is there any better way to accomplish the above task?
• Is there a slick generalization that would allow to compute the problem for multiple endpoint sets $S_1,S_2,\ldots,S_k?$
• Suppose I repeat this process for additional vertices $v_1,v_2,\ldots.$ That is, I first add all possible edges with endpoints in $(v_1,S_1), (v_1,S_2)$ and then proceed with by adding edges with endpoints in $(v_2,S_1) , (v_2,S_2)$, etc.. what is the best way to perform this?
• How does a program like nauty perform the following?
-
If you want advice on using sage, post your question on one of the sage mailing lists. – Chris Godsil Dec 28 '12 at 14:05
@ChrisGodsil No! I just want to make sure if there is any other (=more efficient) way to do what I describe. – Jernej Dec 28 '12 at 16:10
I don't see how you could possibly do it better than by computing orbits of the automorphism group. In order to determine if the graphs are isomorphic or not you're going to have to compute isomorphisms of that nature anyway, so you may as well simplify your work by computing them all at once as a group. I don't see why the same method wouldn't work on structures with the $S_1,\ldots,S_k$ case. – Alexander Gruber Jan 2 '13 at 22:59

Let $H$ be a graph with vertices $u$ and $v$ of degree two, such that $H\backslash u$ and $H\backslash v$ are isomorphic, but $u$ and $v$ lie in different orbits of the automorphism group. Let $G$ be $H\backslash u$ together with an isolated vertex, which will be your fixed vertex. Then we can recover $H$ by adding two edges to two different pairs of vertices, but these pairs are not in the same orbit of $\mathrm{Aut}(G)_v$ (acting on pairs).
To get such an $H$, take a 9-cycle with vertices $\{0,\ldots,8\}$, add three further vertices 9, 10, 11 adjacent respectively to 0, 3, 6, then delete the vertex 8. Then $H\backslash2$ and $H\backslash5$ are isomorphic,