Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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!

share|improve this question
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 –  Gerhard Paseman Jan 16 '13 at 16:54
@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? –  Jernej Jan 16 '13 at 18:55
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 –  Gerhard Paseman Jan 16 '13 at 19:22
If this is feasible, you must have a very large automorphism group. How large is it? –  Brendan McKay Jan 17 '13 at 9:59
@BrendanMcKay the base graph has an automorphism group of order 2^85 * 3^32 * 5^16 * 7^16 –  Jernej Jan 17 '13 at 11:30
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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