[Nauty] from subgraph to supergraph

[Brendan McKay]

* Sterten at aol.com <Sterten at aol.com> [040908 05:14]:
>  
> 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.

No, that does not work.  geng will only generate certain supergraphs and
not all supergraphs.
  
> 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.

Yes.  Unfortunately there is not currently a developed tool for
doing this.  There should be, of course.

Brendan.