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!

  • 2
    $\begingroup$ Are A and B disjoint? Do they start with any edges between them? Do you need to consider anything outside the subgraph of G induced by the vertices in the union of A and B? What do you have in G that suggests a matching of the desired kind is possible? Why should isomorphism classes matter at all (or do you really want all or most nonisomorphic extensions that match A to B)? Gerhard "Ask Me About System Design" Paseman, 2013.01.16 $\endgroup$ Commented Jan 16, 2013 at 16:54
  • 1
    $\begingroup$ @GerhardPaseman A and B are indeed disjoint. And there are no edges between! I don't see any reasons why such a matching would not exists since $B$ is larger then $A.$ Yes, all I really want are nonisomorphic extensions that match $A$ to $B$. BTW, may I ask you about system designs? $\endgroup$
    – Jernej
    Commented Jan 16, 2013 at 18:55
  • $\begingroup$ You certainly may ask. If you have already asked, please remind me again at the previous email address. If you haven't, my registered user page mathoverflow.net/users/3206/gerhard-paseman has a portion of my address. I will have sometime this weekend to post a reply. If you do want all noniso extensions, then it makes sense to consider edges not connecting A to B. Perhaps life would be just as good if you considered just those isomorphisms having A and B as stable sets? Gerhard "Try Being A Smart Brute" Paseman, 2013.01.16 $\endgroup$ Commented Jan 16, 2013 at 19:22
  • $\begingroup$ If this is feasible, you must have a very large automorphism group. How large is it? $\endgroup$ Commented Jan 17, 2013 at 9:59
  • $\begingroup$ @BrendanMcKay the base graph has an automorphism group of order 2^85 * 3^32 * 5^16 * 7^16 $\endgroup$
    – Jernej
    Commented Jan 17, 2013 at 11:30

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.