2
$\begingroup$

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?
  • 0
    If you want advice on using sage, post your question on one of the sage mailing lists.2012-12-28
  • 0
    @ChrisGodsil No! I just want to make sure if there is any other (=more efficient) way to do what I describe.2012-12-28
  • 0
    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.2013-01-02

1 Answers 1