[Nauty] from subgraph to supergraph
Sterten at aol.com
Sterten at aol.com
Wed Sep 8 05:08:01 EST 2004
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
More information about the Nauty
mailing list