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?