[Nauty-list] Generating graphs with fixed induced subgraph

Marko Milosevic ninja643 at gmail.com
Fri Feb 8 23:36:36 EST 2008

On Feb 8, 2008 1:16 PM, Brendan McKay <bdm at cs.anu.edu.au> wrote:

> Gunnar reasonably wonders whether we really agree on the definition,
> but let me answer the question as I understand it. We want to make
> all the graphs on k+t vertices with a specified induced subgraph in
> the first k vertices. Isomorphisms between two such graphs must map
> the first k vertices of one to the first k vertices of the other
> (this is the point that Gunnar highlighted).

Yes, that is what I want to do.

> There is no software in the nauty suite that covers this, but it
> is reasonably routine. Suppose we have all the graphs with k+t-1
> vertices. Let G be such a graph. Let A be its automorphism group
> fixing the first k vertices. Take a new vertex v and join it to
> some subset S of the vertices of G to make H. (We need to consider
> exactly one such S out of each equivalence class of possibilities
> under the action of S on the power set of V(G).) Now compute the
> group B and canonical labelling of H, in each case with the first
> k vertices fixed. Accept H if v is in the same orbit of B as the
> vertex which is last in the canonical labelling; otherwise reject H.
> The set of all such accepted graphs is the complete collection with
> k+t vertices.
> There are many variations and optimizations.

Thank you very much for your time. I will try this.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20080208/a9f1d7bb/attachment.html 

More information about the Nauty mailing list