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

2013-01-16T13:29:15Z

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| = 40, |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!

Answer by Brendan McKay for Generating non-isomorphic graphs by adding edges to a given graph

2013-01-17T11:49:59Z

Let me assume that Aut$(G)$ fixes $A$ and $B$ setwise, or at least the group you use to define equivalence is the setwise stabiliser of each of $A$ and $B$ (in which case use vertex colours to get this stabiliser).

Suppose recursively that you have all the non-equivalent graphs in which $k$ vertices of $A$ are matched to $B$. Do the following for each graph $H$ in that list.

Let $A'$ be the set of vertices of $A$ not matched to $B$ yet, and similarly $B'$. First find the orbits of Aut$(H)$ on $A'\times B'$. For one $e=(a,b)$ from each orbit, consider $H+e$. Compute both Aut$(H+e)$ and a canonical labelling of $H+e$. Accept $H+e$ if $a$ is in the same orbit as the vertex of $A$ which is matched to $B$ and is the first of such vertices in the canonical labelling. Otherwise reject $H+e$.

The set of graphs you accept has exactly one member of each equivalence class of graphs in which $k+1$ vertices of $A$ are matched to $B$. This is the method of "canonical construction path", which some people call "canonical augmentation".

If you write it in depth-first form, you don't need to store the graphs but can output them as they are accepted.

There are various ways to use graph invariants to speed it up in practice. The efficiency will depend on what the group is like for the typical intermediate graph.

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

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

Answer by Brendan McKay for Generating non-isomorphic graphs by adding edges to a given graph