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?
[This is an extended comment, not a solution.] There's a problem here when it comes to adding two edges.
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,