[Nauty-list] Generating graphs with fixed induced subgraph

[Brendan McKay]

Hi Marko,

geng cannot do this.  The logic in geng involves thinking forwards
(adding a vertex) and thinking backwards (deleting a vertex). The
problem is that the backwards thinking does not respect any subgraph
that you are trying to maintain. This messes up the logic.

I wonder if your subgraph is permanently distinguished (as if it has
a colour different from all the new vertices), or if you just want
the graphs that happen to have an induced subgraph isomorphic to
your required subgraph.  The former case is quite a bit easier than
the latter, since the latter requires searching for subgraphs in
addition to the one you started with.

Brendan.


* Marko Milosevic <ninja643 at gmail.com> [080207 02:46]:
> Hi.
> 
> I want to generate all graphs on n vertices that have some fixed graph G as
> an induced subgraph, and that satisfy some conditions on vertex degree (I
> have an upper bound for vertex degree). I would also like to use prune
> function to reject some of the graphs. Best thing would be to start with
> graph G and add one vertex at a time in all possible ways.
> 
> Can I do this using geng?
> 
> Thanks in advance,
> 
> Marko Milo?evi?
> Faculty of Science and Mathematics
> Ni?, Serbia

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list