[Nauty] Generating subgraph-closed graph classes with geng

[Kolja Kühn]

Hello,

I want to use geng to generate graphs from some graph class H. Is there 
a way to tell geng that H is subgraph-closed, for possible optimizations?

This question is based on my rudimentary understanding of what geng 
does: Add to a graph one vertex at a time, and test for all (?) possible 
adjacencies of this vertex whether this vertex would have been the final 
one added in some canonical construction sequence. If not, discard. If 
yes, call the PRUNE macro to possible cut off this branch of the 
generation tree anyway. Is this roughly correct?

I now envision the following: Start with a graph G of H. Add a vertex v 
with neighborhood N(v). Now if PRUNE fails, we don't need to test any of 
the strict superset neighborhoods that the new vertex v could have. 
(regardless of whether or not for this superset we would have been the 
canonical construction sequence; so we save all those tests plus 
possibly some PRUNE tests, if it was indeed the canonical sequence)

Is my rough understanding accurate enough for this to make sense? Is 
this done / could it be done?

Kind regards
Kolja

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4855 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://mailman.anu.edu.au/pipermail/nauty/attachments/20260507/77e43c8d/attachment.p7s>