2 edited body

Hello!

This question is in a way related to the one I posted on math.se. Since the question there did not produce any final answer I am trying my luck here!

I am given a fairly large graph $G$ and subsets $A,B \subseteq V(G)$ where $|A| \leq |B|.$ I need to extend $G$ so that every vertex $v \in A$ is matched with precisely one vertex in $B.$ By matched I mean that $v$ is adjacent to a vertex in $v' \in B$ and no other vertex of $A$ is adjacent to $v'.$

The way I am doing this now is that for each fixed vertex $v \in A$ I compute the orbits of the stabilizer $\rm{Aut}(G)_v$ and then only add edges to representatives of orbits of elements of $B$ that are still "free."

The problem with this approach is that we still obtain isomorphic graphs after we repeat the above procedure on the new graphs and for the next unmatched vertex. To patch this I also keep a list of canonical labelings for each graph as to ensure that each step gives only non isomorphic graphs.

Now the problem is that the described approach is inefficient for my concrete case $(|A| = 3840, |B| = 48).$ Since $G$ is highly-symmetric I am fairly confident that the number of all non-isomorphic graphs obtained by matching all vertices in $A$ is manageable but computing automorphism groups and canonical labelings after every iteration appears to slow down things a lot.

Hence I am wondering if there is any other more efficient way to do this? Perhaps something based on computing the canonical labeling of $G$ at the start and then adding edges as to preserve the labeling?

I am not really knowledgeable of what can be done but since I would really like to generate these graphs I'd be thankful for any constructive suggestion!

1

# Generating non-isomorphic graphs by adding edges to a given graph

Hello!

This question is in a way related to the one I posted on math.se. Since the question there did not produce any final answer I am trying my luck here!

I am given a fairly large graph $G$ and subsets $A,B \subseteq V(G)$ where $|A| \leq |B|.$ I need to extend $G$ so that every vertex $v \in A$ is matched with precisely one vertex in $B.$ By matched I mean that $v$ is adjacent to a vertex in $v' \in B$ and no other vertex of $A$ is adjacent to $v'.$

The way I am doing this now is that for each fixed vertex $v \in A$ I compute the orbits of the stabilizer $\rm{Aut}(G)_v$ and then only add edges to representatives of orbits of elements of $B$ that are still "free."

The problem with this approach is that we still obtain isomorphic graphs after we repeat the above procedure on the new graphs and for the next unmatched vertex. To patch this I also keep a list of canonical labelings for each graph as to ensure that each step gives only non isomorphic graphs.

Now the problem is that the described approach is inefficient for my concrete case $(|A| = 38, |B| = 48).$ Since $G$ is highly-symmetric I am fairly confident that the number of all non-isomorphic graphs obtained by matching all vertices in $A$ is manageable but computing automorphism groups and canonical labelings after every iteration appears to slow down things a lot.

Hence I am wondering if there is any other more efficient way to do this? Perhaps something based on computing the canonical labeling of $G$ at the start and then adding edges as to preserve the labeling?

I am not really knowledgeable of what can be done but since I would really like to generate these graphs I'd be thankful for any constructive suggestion!