[Nauty] from subgraph to supergraph

[Sterten at aol.com]

In einer eMail vom 07.09.2004 12:57:47 Westeuropäische Sommerzeit schreibt  
zstanic at matf.bg.ac.yu:

I hope  that somebody can give me answer on this: Is it possible to
obtain  all
nonisomorfic supergraphs (on specified number of nodes) of given  graph
by using of some program from Nauty package? For example, if I have  one
graph on (let I say) 8
nodes, can I obtain all graphs on 10 nodes  which consist the previous
graph as its  subgraph?

Zoran



---------------------------------------------
 
you can use the "prune" in geng.c .
if n=8, then check whether the submitted graph is isomorphic to the  required 
graph.
 
or do it by yourself:
add a new 9th vertex, connect it to each possible subset of the 8  vertices.
call canonize on the 2^8 graphs
sort out the doublettes
add a 10ths vertex to each of the remaining supergraphs with 9  vertices
connect it to each subset of the 9 other vertices
etc.
 
 
Guenter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20040908/6e37ef2f/attachment.html